libcore/DisplayList.cpp

   1 // dlist.cpp:    Display lists, for Gnash.
   2 //
   3 //     Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010 Free Software
   4 //     Foundation, Inc
   5 //
   6 // This program is free software; you can redistribute it and/or modify
   7 // it under the terms of the GNU General Public License as published by
   8 // the Free Software Foundation; either version 3 of the License, or
   9 // (at your option) any later version.
  10 //
  11 // This program is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.    See the
  14 // GNU General Public License for more details.
  15 //
  16 // You should have received a copy of the GNU General Public License
  17 // along with this program; if not, write to the Free Software
  18 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA    02110-1301    USA
  19 //
  20
  21 #include "smart_ptr.h" // GNASH_USE_GC
  22 #include "DisplayList.h"
  23 #include "log.h"
  24 #include "Renderer.h"
  25 #include "StringPredicates.h"
  26 #include "MovieClip.h"
  27
  28 #include <typeinfo>
  29 #include <iostream>
  30 #include <algorithm>
  31 #include <stack>
  32 #include <cassert>
  33 #include <boost/bind.hpp>
  34
  35 namespace gnash {
  36
  37 // Forward declarations
  38 namespace {
  39         /// Return an iterator to the first element of the container NOT
  40     /// in the "removed" depth zone
  41     DisplayList::iterator beginNonRemoved(DisplayList::container_type& c);
  42
  43         /// Return an constant iterator to the first element of the
  44     /// container NOT in the "removed" depth zone
  45     DisplayList::const_iterator beginNonRemoved(
  46             const DisplayList::container_type& c);
  47
  48         /// Return an iterator succeeding the last element in zone
  49     /// (-16384, 0xffff-16384)
  50     DisplayList::iterator dlistTagsEffectiveZoneEnd(
  51             DisplayList::container_type& c);
  52
  53         /// Return an constant iterator succeeding the last element
  54     /// in (-16384, 0xffff-16384)
  55     DisplayList::const_iterator dlistTagsEffectiveZoneEnd(
  56             const DisplayList::container_type& c);
  57 }
  58
  59 /// Anonymous namespace for generic algorithm functors.
  60 namespace {
  61
  62 class DepthEquals
  63 {
  64 public:
  65
  66     DepthEquals(int depth) : _depth(depth) {}
  67
  68     bool operator() (const DisplayObject* item) {
  69         if (!item) return false;
  70         return item->get_depth() == _depth;
  71     }
  72
  73 private:
  74     int _depth;
  75 };
  76
  77 struct DepthGreaterThan
  78 {
  79     bool operator()(const DisplayObject* a, const DisplayObject* b) {
  80         return a->get_depth() > b->get_depth();
  81     }
  82 };
  83
  84 struct DepthLessThan
  85 {
  86     bool operator()(const DisplayObject* a, const DisplayObject* b) {
  87         return a->get_depth() < b->get_depth();
  88     }
  89 };
  90
  91 class DepthGreaterOrEqual
  92 {
  93 public:
  94
  95     DepthGreaterOrEqual(int depth) : _depth(depth) {}
  96
  97     bool operator() (const DisplayObject* item) {
  98         if (!item) return false;
  99         return item->get_depth() >= _depth;
 100     }
 101 private:
 102     int _depth;
 103 };
 104
 105
 106 class NameEquals
 107 {
 108 public:
 109     NameEquals(string_table& st, const ObjectURI& uri, bool caseless)
 110         :
 111         _st(st),
 112         _caseless(caseless),
 113         _name(uri)
 114     {}
 115
 116     bool operator() (const DisplayObject* item) {
 117         assert (item);
 118
 119         // TODO: this is necessary because destroy() is called in
 120         // movie_root, leaving destroyed items on the DisplayList. They
 121         // shouldn't be found. A better fix would be to stop destroying
 122         // objects there and add to the invariant that there are never
 123         // destroyed DisplayObjects in the DisplayList.
 124         if (item->isDestroyed()) return false;
 125
 126         if ( _caseless ) {
 127             return equalsNoCase(_st, item->get_name(), _name);
 128         } else {
 129             return item->get_name() ==  _name;
 130         }
 131     }
 132
 133 private:
 134     string_table& _st;
 135     const bool _caseless;
 136     const ObjectURI& _name;
 137 };
 138
 139 } // anonymous namespace
 140
 141 int
 142 DisplayList::getNextHighestDepth() const
 143 {
 144     testInvariant();
 145
 146     int nexthighestdepth=0;
 147     for (const_iterator it = _charsByDepth.begin(),
 148             itEnd = _charsByDepth.end(); it != itEnd; ++it) {
 149
 150         DisplayObject* ch = *it;
 151
 152         int chdepth = ch->get_depth();
 153         if (chdepth >= nexthighestdepth) {
 154             nexthighestdepth = chdepth+1;
 155         }
 156     }
 157     return nexthighestdepth;
 158 }
 159
 160 DisplayObject*
 161 DisplayList::getDisplayObjectAtDepth(int depth) const
 162 {
 163     testInvariant();
 164
 165     for (const_iterator it = _charsByDepth.begin(), itEnd = _charsByDepth.end();
 166         it != itEnd; ++it) {
 167
 168         DisplayObject* ch = *it;
 169
 170         // Should not be there!
 171         if (ch->isDestroyed()) continue;
 172
 173         // found
 174         if (ch->get_depth() == depth) return ch;
 175
 176         // non-existent (chars are ordered by depth)
 177         if (ch->get_depth() > depth) return 0;
 178     }
 179
 180     return 0;
 181
 182 }
 183
 184
 185 DisplayObject*
 186 DisplayList::getDisplayObjectByName(string_table& st, const ObjectURI& uri,
 187         bool caseless) const
 188 {
 189     testInvariant();
 190
 191     const container_type::const_iterator e = _charsByDepth.end();
 192
 193     container_type::const_iterator it =
 194         std::find_if(_charsByDepth.begin(), e, NameEquals(st, uri, caseless));
 195
 196     if (it == e) return 0;
 197
 198     return *it;
 199
 200 }
 201
 202 void
 203 DisplayList::placeDisplayObject(DisplayObject* ch, int depth)
 204 {
 205     assert(!ch->unloaded());
 206     ch->set_invalidated();
 207     ch->set_depth(depth);
 208
 209     container_type::iterator it =
 210         std::find_if( _charsByDepth.begin(), _charsByDepth.end(),
 211                 DepthGreaterOrEqual(depth));
 212
 213     if (it == _charsByDepth.end() || (*it)->get_depth() != depth) {
 214         // add the new char
 215         _charsByDepth.insert(it, ch);
 216     }
 217     else {
 218         // remember bounds of old char
 219         InvalidatedRanges old_ranges;
 220         (*it)->add_invalidated_bounds(old_ranges, true);
 221
 222         // make a copy (before replacing)
 223         DisplayObject* oldCh = *it;
 224
 225         // replace existing char (before calling unload!)
 226         *it = ch;
 227
 228         if (oldCh->unload()) {
 229             // reinsert removed DisplayObject if needed
 230             reinsertRemovedCharacter(oldCh);
 231         }
 232         else oldCh->destroy();
 233
 234         // extend invalidated bounds
 235         ch->extend_invalidated_bounds(old_ranges);
 236     }
 237
 238     testInvariant();
 239 }
 240
 241 void
 242 DisplayList::add(DisplayObject* ch, bool replace)
 243 {
 244     int depth = ch->get_depth();
 245
 246     container_type::iterator it =
 247         std::find_if(_charsByDepth.begin(), _charsByDepth.end(),
 248                 DepthGreaterOrEqual(depth));
 249
 250     if (it == _charsByDepth.end() || (*it)->get_depth() != depth) {
 251         _charsByDepth.insert(it, ch);
 252     }
 253     else if (replace) *it = ch;
 254
 255     testInvariant();
 256 }
 257
 258 void
 259 DisplayList::replaceDisplayObject(DisplayObject* ch, int depth,
 260         bool use_old_cxform, bool use_old_matrix)
 261 {
 262     testInvariant();
 263
 264     //GNASH_REPORT_FUNCTION;
 265     assert(!ch->unloaded());
 266
 267     ch->set_invalidated();
 268     ch->set_depth(depth);
 269
 270     container_type::iterator it =
 271         std::find_if(_charsByDepth.begin(), _charsByDepth.end(),
 272             DepthGreaterOrEqual(depth));
 273
 274     if (it == _charsByDepth.end() || (*it)->get_depth() != depth) {
 275         _charsByDepth.insert(it, ch);
 276     }
 277     else {
 278         // Make a copy (before replacing)
 279         DisplayObject* oldch = *it;
 280
 281         InvalidatedRanges old_ranges;
 282
 283         if (use_old_cxform) {
 284             // Use the SWFCxForm from the old DisplayObject.
 285             ch->setCxForm(getCxForm(*oldch));
 286         }
 287
 288         if (use_old_matrix) {
 289             // Use the SWFMatrix from the old DisplayObject.
 290             ch->setMatrix(getMatrix(*oldch), true);
 291         }
 292
 293         // remember bounds of old char
 294         oldch->add_invalidated_bounds(old_ranges, true);
 295
 296         // replace existing char (before calling unload)
 297         *it = ch;
 298
 299         // Unload old char
 300         if (oldch->unload()) {
 301             // reinsert removed DisplayObject if needed
 302             reinsertRemovedCharacter(oldch);
 303         }
 304         else oldch->destroy();
 305
 306         // extend invalidated bounds
 307         // WARNING: when a new Button DisplayObject is added,
 308         //          the invalidated bounds computation will likely
 309         //          be bogus, as the actual DisplayObject shown is not
 310         //          instantiated until stagePlacementCallback for buttons
 311         //          (I'd say this is a bug in Button).
 312         ch->extend_invalidated_bounds(old_ranges);
 313
 314     }
 315
 316     testInvariant();
 317 }
 318
 319
 320 // Updates the transform properties of the DisplayObject at
 321 // the specified depth.
 322 void
 323 DisplayList::moveDisplayObject( int depth, const SWFCxForm* color_xform,
 324         const SWFMatrix* mat, int* ratio, int* /* clip_depth */)
 325 {
 326     testInvariant();
 327
 328     DisplayObject* ch = getDisplayObjectAtDepth(depth);
 329     if (! ch) {
 330         // FIXME, should this be log_aserror?
 331         IF_VERBOSE_MALFORMED_SWF(
 332         log_swferror(_("moveDisplayObject() -- can't find object at depth %d"),
 333             depth);
 334         );
 335         return;
 336     }
 337
 338     if (ch->unloaded()) {
 339         log_error("Request to move an unloaded DisplayObject");
 340         assert(!ch->unloaded());
 341     }
 342
 343     // TODO: is sign of depth related to accepting anim moves ?
 344     if (!ch->get_accept_anim_moves()) {
 345         // This DisplayObject is rejecting anim moves.    This happens after it
 346         // has been manipulated by ActionScript.
 347         return;
 348     }
 349
 350     if (color_xform) ch->setCxForm(*color_xform);
 351     if (mat) ch->setMatrix(*mat, true);
 352     if (ratio) ch->set_ratio(*ratio);
 353
 354     testInvariant();
 355 }
 356
 357
 358 // Removes the object at the specified depth.
 359 void
 360 DisplayList::removeDisplayObject(int depth)
 361 {
 362     //GNASH_REPORT_FUNCTION;
 363
 364     testInvariant();
 365
 366 #ifndef NDEBUG
 367     container_type::size_type size = _charsByDepth.size();
 368 #endif
 369
 370     // TODO: would it be legal to call removeDisplayObject with a depth
 371     //             in the "removed" zone ?
 372     // TODO: optimize to take by-depth order into account
 373     container_type::iterator it =
 374         std::find_if( _charsByDepth.begin(), _charsByDepth.end(),
 375             DepthEquals(depth));
 376
 377     if (it != _charsByDepth.end()) {
 378         // Make a copy (before erasing)
 379         DisplayObject* oldCh = *it;
 380
 381         // Erase (before calling unload)
 382         _charsByDepth.erase(it);
 383
 384         if (oldCh->unload()) {
 385             // reinsert removed DisplayObject if needed
 386             // NOTE: could be optimized if we knew exactly how
 387             //             to handle the case in which the target depth
 388             //             (after the shift) is occupied already
 389             //
 390             reinsertRemovedCharacter(oldCh);
 391         }
 392         else oldCh->destroy();
 393     }
 394
 395     assert(size >= _charsByDepth.size());
 396
 397     testInvariant();
 398
 399 }
 400
 401 // TODO: take DisplayObject by ref ?
 402 void
 403 DisplayList::swapDepths(DisplayObject* ch1, int newdepth)
 404 {
 405     testInvariant();
 406
 407     if (newdepth < DisplayObject::staticDepthOffset) {
 408         IF_VERBOSE_ASCODING_ERRORS(
 409         log_aserror("%s.swapDepth(%d) : ignored call with target depth "
 410             "less then %d", ch1->getTarget(), newdepth,
 411             DisplayObject::staticDepthOffset);
 412         );
 413         return;
 414     }
 415
 416     const int srcdepth = ch1->get_depth();
 417
 418     // what if source char is at a lower depth ?
 419     assert(srcdepth >= DisplayObject::staticDepthOffset);
 420
 421     assert(srcdepth != newdepth);
 422
 423     // TODO: optimize this scan by taking ch1 depth into account ?
 424     container_type::iterator it1 =
 425         std::find(_charsByDepth.begin(), _charsByDepth.end(), ch1);
 426
 427     // upper bound ...
 428     container_type::iterator it2 =
 429         std::find_if(_charsByDepth.begin(), _charsByDepth.end(),
 430             DepthGreaterOrEqual(newdepth));
 431
 432     if (it1 == _charsByDepth.end()) {
 433         log_error("First argument to DisplayList::swapDepth() "
 434                 "is NOT a DisplayObject in the list. Call ignored.");
 435         return;
 436     }
 437
 438     // Found another DisplayObject at the given depth
 439     if (it2 != _charsByDepth.end() && (*it2)->get_depth() == newdepth)
 440     {
 441         DisplayObject* ch2 = *it2;
 442
 443         ch2->set_depth(srcdepth);
 444
 445         // TODO: we're not actually invalidated ourselves, rather
 446         // our parent is...
 447         ch2->set_invalidated();
 448
 449         // We won't accept static transforms after a depth swap.
 450         // See displaylist_depths_test6.swf for more info.
 451         ch2->transformedByScript();
 452
 453         std::iter_swap(it1, it2);
 454     }
 455
 456     // No DisplayObject found at the given depth
 457     else {
 458         // Move the DisplayObject to the new position
 459         // NOTE: insert *before* erasing, in case the list is
 460         //             the only referer of the ref-counted DisplayObject
 461         _charsByDepth.insert(it2, ch1);
 462         _charsByDepth.erase(it1);
 463     }
 464
 465     // don't change depth before the iter_swap case above, as
 466     // we'll need it to assign to the new DisplayObject
 467     ch1->set_depth(newdepth);
 468
 469     // TODO: we're not actually invalidated ourselves, rather our parent is...
 470     //             UdoG ? Want to verify this ?
 471     ch1->set_invalidated();
 472
 473     // We won't accept static transforms after a depth swap.
 474     // See displaylist_depths_test6.swf for more info.
 475     ch1->transformedByScript();
 476
 477     testInvariant();
 478
 479 }
 480
 481 DisplayObject*
 482 DisplayList::removeDisplayObjectAt(int index)
 483 {
 484     container_type::iterator it =
 485         std::find_if(_charsByDepth.begin(), _charsByDepth.end(),
 486                 DepthEquals(index));
 487
 488     if (it == _charsByDepth.end()) return 0;
 489
 490     DisplayObject* obj = *it;
 491     _charsByDepth.erase(it);
 492     return obj;
 493 }
 494
 495 void
 496 DisplayList::removeDisplayObject(DisplayObject* obj)
 497 {
 498     container_type::iterator it = std::find(_charsByDepth.begin(),
 499             _charsByDepth.end(), obj);
 500
 501     if (it != _charsByDepth.end()) {
 502         _charsByDepth.erase(it);
 503     }
 504 }
 505
 506 void
 507 DisplayList::insertDisplayObject(DisplayObject* obj, int index)
 508 {
 509     testInvariant();
 510
 511     assert(!obj->unloaded());
 512
 513     obj->set_invalidated();
 514     obj->set_depth(index);
 515
 516     // Find the first index greater than or equal to the required index
 517     container_type::iterator it =
 518         std::find_if(_charsByDepth.begin(), _charsByDepth.end(),
 519             DepthGreaterOrEqual(index));
 520
 521     // Insert the DisplayObject before that position
 522     _charsByDepth.insert(it, obj);
 523
 524     // Shift depths upwards until no depths are duplicated. No DisplayObjects
 525     // are removed!
 526     while (it != _charsByDepth.end() && (*it)->get_depth() == index) {
 527         (*it)->set_depth(index + 1);
 528         ++index, ++it;
 529     }
 530
 531     testInvariant();
 532
 533 }
 534
 535 void
 536 DisplayList::addDisplayObject(DisplayObject* obj)
 537 {
 538     testInvariant();
 539
 540     assert(!obj->unloaded());
 541
 542     obj->set_invalidated();
 543
 544     int index;
 545
 546     if (_charsByDepth.empty()) {
 547         index = 0;
 548     }
 549     else {
 550         container_type::const_reverse_iterator it = _charsByDepth.rbegin();
 551         index = (*it)->get_depth() + 1;
 552     }
 553
 554     obj->set_depth(index);
 555
 556     // Insert the DisplayObject at the end
 557     _charsByDepth.insert(_charsByDepth.end(), obj);
 558
 559     testInvariant();
 560
 561 }
 562
 563
 564 bool
 565 DisplayList::unload()
 566 {
 567     testInvariant();
 568
 569     bool unloadHandler = false;
 570
 571     // All children with an unload handler should be unloaded. As soon as
 572     // the first unload handler is encountered, subsequent children should
 573     // not be destroyed or removed from the display list. This affects
 574     // children without an unload handler.
 575     for (iterator it = beginNonRemoved(_charsByDepth),
 576             itEnd = _charsByDepth.end(); it != itEnd; )
 577     {
 578         // make a copy
 579         DisplayObject* di = *it;
 580
 581         // Destroyed objects should not be there!
 582         assert(!di->isDestroyed());
 583
 584         // Destroy those with a handler anyway?
 585         if (di->unload()) {
 586             unloadHandler = true;
 587             ++it;
 588             continue;
 589         }
 590
 591         if (!unloadHandler) {
 592             di->destroy();
 593             it = _charsByDepth.erase(it);
 594         }
 595         else ++it;
 596
 597     }
 598
 599     testInvariant();
 600
 601     return unloadHandler;
 602
 603 }
 604
 605
 606 void
 607 DisplayList::destroy()
 608 {
 609     //GNASH_REPORT_FUNCTION;
 610
 611     testInvariant();
 612
 613     for (iterator it = _charsByDepth.begin(), itEnd = _charsByDepth.end();
 614             it != itEnd; ) {
 615
 616         // make a copy
 617         DisplayObject* di = *it;
 618
 619         // skip if already unloaded
 620         if ( di->isDestroyed() ) {
 621             ++it;
 622             continue;
 623         }
 624
 625         di->destroy();
 626         it = _charsByDepth.erase(it);
 627     }
 628     testInvariant();
 629 }
 630
 631 // Display the referenced DisplayObjects. Lower depths
 632 // are obscured by higher depths.
 633 void
 634 DisplayList::display(Renderer& renderer, const Transform& base)
 635 {
 636     testInvariant();
 637
 638     std::stack<int> clipDepthStack;
 639
 640     // We only display DisplayObjects which are out of the "removed" zone
 641     // (or should we check unloaded?)
 642     iterator it = beginNonRemoved(_charsByDepth);
 643     for (iterator endIt = _charsByDepth.end(); it != endIt; ++it)
 644     {
 645         DisplayObject* ch = *it;
 646         assert(!ch->isDestroyed());
 647
 648         // Don't display dynamic masks
 649         if (ch->isDynamicMask()) continue;
 650
 651         assert(!ch->unloaded()); // we don't advance unloaded chars
 652
 653         // Check if this charater or any of its parents is a mask.
 654         // Characters acting as masks should always be rendered to the
 655         // mask buffer despite their visibility.
 656         //
 657         DisplayObject* p = ch->parent();
 658         bool renderAsMask = ch->isMaskLayer();
 659
 660         while (!renderAsMask && p) {
 661             renderAsMask = p->isMaskLayer();
 662             p = p->parent();
 663         }
 664
 665         // check for non-mask hiden DisplayObjects
 666         if (!renderAsMask && (!ch->visible())) {
 667             ch->omit_display();
 668             // Don't display non-mask hidden DisplayObjects
 669             continue;
 670         }
 671
 672         int depth = ch->get_depth();
 673         // Discard useless masks
 674         while (!clipDepthStack.empty() && (depth > clipDepthStack.top())) {
 675             clipDepthStack.pop();
 676             renderer.disable_mask();
 677         }
 678
 679         // Push a new mask to the masks stack
 680         if (ch->isMaskLayer()) {
 681             const int clipDepth = ch->get_clip_depth();
 682             clipDepthStack.push(clipDepth);
 683             renderer.begin_submit_mask();
 684         }
 685
 686         if (ch->boundsInClippingArea(renderer)) {
 687             ch->display(renderer, base);
 688         }
 689         else ch->omit_display();
 690
 691         // Notify the renderer that mask drawing has finished.
 692         if (ch->isMaskLayer()) renderer.end_submit_mask();
 693     }
 694
 695     // Discard any remaining masks
 696     while (!clipDepthStack.empty()) {
 697         clipDepthStack.pop();
 698         renderer.disable_mask();
 699     }
 700
 701
 702 }
 703
 704 void
 705 DisplayList::omit_display()
 706 {
 707     iterator it = beginNonRemoved(_charsByDepth);
 708     for (iterator endIt = _charsByDepth.end(); it != endIt; ++it) {
 709         DisplayObject* ch = *it;
 710         ch->omit_display();
 711     }
 712 }
 713
 714 void
 715 DisplayList::dump() const
 716 {
 717     //testInvariant();
 718
 719     if ( _charsByDepth.empty() ) return;
 720
 721     string_table& st = getStringTable(*getObject(_charsByDepth.front()));
 722     ObjectURI::Logger l(st);
 723
 724     int num=0;
 725     for (const_iterator it = _charsByDepth.begin(),
 726             endIt = _charsByDepth.end(); it != endIt; ++it) {
 727
 728         const DisplayObject* dobj = *it;
 729         log_debug(_("Item %d(%s) at depth %d (char name %s, type %s)"
 730                     "Destroyed: %s, unloaded: %s"),
 731             num, dobj, dobj->get_depth(), l.debug(dobj->get_name()), typeName(*dobj),
 732             dobj->isDestroyed(), dobj->unloaded());
 733         num++;
 734     }
 735 }
 736
 737
 738 void
 739 DisplayList::add_invalidated_bounds(InvalidatedRanges& ranges, bool force)
 740 {
 741     testInvariant();
 742
 743     // This function generally has nothing else to do than calling the
 744     // add_invalidated_bounds() function of all items in the display list.
 745     // However, special optimization is included for masks, which makes it
 746     // look a bit more complicated. We want to avoid that a masked DisplayObject
 747     // invalidates an area where the DisplayObject is invisible because of it's
 748     // mask (which is quite common). For example, think of a large bitmap that
 749     // covers the entire stage and is masked by a very small circle in the
 750     // middle of the stage (ie. it's only visible there). Changes in the
 751     // bitmap sprite would invalidate the whole stage even if only the small
 752     // masked portion in the middle really needs to be drawn again.
 753     //
 754     // So, like display(), we keep a stack of masks. Instead of drawing the
 755     // mask we keep a separate list of InvalidatedRanges for the masks which
 756     // later are intersected with the masked DisplayObjects' InvalidatedRanges.
 757     //
 758     // The code is much based on the display() function, so some references
 759     // in comments have been added for convenience.
 760     //
 761     // For a simpler implementation (that doesn't care about masks, but
 762     // still produces correct results) see CVS revision 1.96
 763
 764     // TODO: review this function to take "dynamic" mask and maskees
 765     // into account
 766
 767     std::stack<int> clipDepthStack; // same method used in display()
 768     std::stack<InvalidatedRanges> rangesStack;
 769     bool drawing_mask = false;
 770
 771     iterator it = beginNonRemoved(_charsByDepth);
 772     for (iterator endIt = _charsByDepth.end(); it != endIt; ++it) {
 773         DisplayObject* dobj = *it;
 774
 775 #ifndef GNASH_USE_GC
 776         assert(dobj->get_ref_count() > 0);
 777 #endif // ndef GNASH_USE_GC
 778
 779
 780         const int depth = dobj->get_depth();
 781
 782         // Discard useless masks
 783         while (!clipDepthStack.empty() && (depth > clipDepthStack.top())) {
 784             clipDepthStack.pop();
 785             rangesStack.pop();    // disable_mask() equivalent
 786
 787         }
 788
 789         // Push a new mask to the masks stack
 790         if (dobj->isMaskLayer()) {
 791
 792             const int clipDepth = dobj->get_clip_depth();
 793             clipDepthStack.push(clipDepth);
 794
 795             drawing_mask = true; // begin_submit_mask equivalent
 796
 797             if (rangesStack.empty()) {
 798                 InvalidatedRanges item;
 799                 rangesStack.push(item);
 800             }
 801             else {
 802                 // copy the top mask
 803                 rangesStack.push(rangesStack.top());
 804             }
 805         }
 806
 807         if (drawing_mask) {
 808
 809             // --> The child is part of a mask, so add ranges to our
 810             // mask ranges stack
 811
 812             assert(!rangesStack.empty());
 813             dobj->add_invalidated_bounds(rangesStack.top(), true);
 814
 815             // need to call add_invalidated_bounds again because the previous
 816             // call needs force==true. Changes to the mask itself may also
 817             // require re-rendering of the mask area, so we have to
 818             // add the mask itself to the global ranges, but this time
 819             // with normal "force" value...
 820             // As long the mask has not been invalidated and force==false this
 821             // call won't modify the "ranges" list.
 822             dobj->add_invalidated_bounds(ranges, force);
 823
 824         }
 825         else {
 826
 827             if (rangesStack.empty()) {
 828
 829                 // --> normal case for unmasked DisplayObjects
 830                 dobj->add_invalidated_bounds(ranges, force);
 831
 832             }
 833             else {
 834
 835                 // --> DisplayObject is masked, so intersect with "mask"
 836
 837                 // first get the ranges of the child in a separate list
 838                 InvalidatedRanges childRanges;
 839                 childRanges.inheritConfig(ranges);
 840
 841                 dobj->add_invalidated_bounds(childRanges, force);
 842
 843                 // then intersect ranges with topmost "mask"
 844                 childRanges.intersect(rangesStack.top());
 845
 846                 // add result to the global ranges
 847                 ranges.add(childRanges);
 848
 849             }
 850
 851         } // not drawing mask
 852
 853         // <== end of display() equivalent
 854
 855
 856         // Mask "drawing" has finished
 857         if (dobj->isMaskLayer()) {
 858             // end_submit_mask equivalent
 859             drawing_mask = false;
 860         }
 861     }
 862
 863
 864 }
 865
 866 void
 867 DisplayList::sort()
 868 {
 869     _charsByDepth.sort(DepthLessThan());
 870 }
 871
 872 void
 873 DisplayList::mergeDisplayList(DisplayList & newList)
 874 {
 875     testInvariant();
 876
 877     iterator itOld = beginNonRemoved(_charsByDepth);
 878     iterator itNew = beginNonRemoved(newList._charsByDepth);
 879
 880     iterator itOldEnd = dlistTagsEffectiveZoneEnd(_charsByDepth);
 881     iterator itNewEnd = newList._charsByDepth.end();
 882     assert(itNewEnd == dlistTagsEffectiveZoneEnd(newList._charsByDepth) );
 883
 884     // step1.
 885     // starting scanning both lists.
 886     while (itOld != itOldEnd)
 887     {
 888         iterator itOldBackup = itOld;
 889
 890         DisplayObject* chOld = *itOldBackup;
 891         int depthOld = chOld->get_depth();
 892
 893         while (itNew != itNewEnd) {
 894             iterator itNewBackup = itNew;
 895
 896             DisplayObject* chNew = *itNewBackup;
 897             int depthNew = chNew->get_depth();
 898
 899             // depth in old list is occupied, and empty in new list.
 900             if (depthOld < depthNew) {
 901
 902                 itOld++;
 903                 // unload the DisplayObject if it's in static zone(-16384,0)
 904                 if (depthOld < 0) {
 905                     _charsByDepth.erase(itOldBackup);
 906
 907                      if (chOld->unload()) reinsertRemovedCharacter(chOld);
 908                      else chOld->destroy();
 909                 }
 910
 911                 break;
 912             }
 913             // depth is occupied in both lists
 914
 915             if (depthOld == depthNew) {
 916                 ++itOld;
 917                 ++itNew;
 918
 919                 bool is_ratio_compatible =
 920                     (chOld->get_ratio() == chNew->get_ratio());
 921
 922                 if (!is_ratio_compatible || chOld->isDynamic() ||
 923                         !isReferenceable(*chOld)) {
 924                     // replace the DisplayObject in old list with
 925                     // corresponding DisplayObject in new list
 926                     _charsByDepth.insert(itOldBackup, *itNewBackup);
 927                     _charsByDepth.erase(itOldBackup);
 928
 929                     // unload the old DisplayObject
 930                     if (chOld->unload()) reinsertRemovedCharacter(chOld);
 931                     else chOld->destroy();
 932                 }
 933                 else {
 934                     newList._charsByDepth.erase(itNewBackup);
 935
 936                     // replace the transformation SWFMatrix if the old
 937                     // DisplayObject accepts static transformation.
 938                     if (chOld->get_accept_anim_moves()) {
 939                         chOld->setMatrix(getMatrix(*chNew), true);
 940                         chOld->setCxForm(getCxForm(*chNew));
 941                     }
 942                     chNew->unload();
 943                     chNew->destroy();
 944                 }
 945
 946                 break;
 947             }
 948
 949             // depth in old list is empty, but occupied in new list.
 950             ++ itNew;
 951             // add the new DisplayObject to the old list.
 952             _charsByDepth.insert(itOldBackup, *itNewBackup );
 953         }
 954
 955         // break if finish scanning the new list
 956         if (itNew == itNewEnd) break;
 957     }
 958
 959     // step2(only required if scanning of new list finished earlier in step1).
 960     // continue to scan the static zone of the old list.
 961     // unload remaining DisplayObjects directly.
 962     while((itOld != itOldEnd) && ((*itOld)->get_depth() < 0)) {
 963
 964         DisplayObject* chOld = *itOld;
 965         itOld = _charsByDepth.erase(itOld);
 966
 967         if (chOld->unload()) reinsertRemovedCharacter(chOld);
 968         else chOld->destroy();
 969     }
 970
 971     // step3(only required if scanning of old list finished earlier in step1).
 972     // continue to scan the new list.
 973     // add remaining DisplayObjects directly.
 974     if (itNew != itNewEnd) _charsByDepth.insert(itOld, itNew, itNewEnd);
 975
 976     // step4.
 977     // Copy all unloaded DisplayObjects from the new display list to the
 978     // old display list, and clear the new display list
 979     for (itNew = newList._charsByDepth.begin(); itNew != itNewEnd; ++itNew) {
 980
 981         DisplayObject* chNew = *itNew;
 982         int depthNew = chNew->get_depth();
 983
 984         if (chNew->unloaded()) {
 985             iterator it =
 986                 std::find_if(_charsByDepth.begin(), _charsByDepth.end(),
 987                     DepthGreaterOrEqual(depthNew));
 988
 989             _charsByDepth.insert(it, *itNew);
 990         }
 991     }
 992
 993     // clear the new display list after merge
 994     // ASSERT:
 995     //     - Any element in newList._charsByDepth is either marked as unloaded
 996     //    or found in this list
 997 #if GNASH_PARANOIA_LEVEL > 1
 998     for (iterator i = newList._charsByDepth.begin(),
 999             e = newList._charsByDepth.end(); i != e; ++i) {
1000
1001         DisplayObject* ch = *i;
1002         if (!ch->unloaded()) {
1003
1004             iterator found =
1005                 std::find(_charsByDepth.begin(), _charsByDepth.end(), ch);
1006
1007             if (found == _charsByDepth.end())
1008             {
1009                 log_error("mergeDisplayList: DisplayObject %s (%s at depth "
1010                         "%d [%d]) about to be discarded in given display list"
1011                         " is not marked as unloaded and not found in the"
1012                         " merged current displaylist",
1013                         ch->getTarget(), typeName(*ch), ch->get_depth(),
1014                         ch->get_depth()-DisplayObject::staticDepthOffset);
1015                 std::abort();
1016             }
1017         }
1018     }
1019 #endif
1020     newList._charsByDepth.clear();
1021
1022     testInvariant();
1023 }
1024
1025
1026 void
1027 DisplayList::reinsertRemovedCharacter(DisplayObject* ch)
1028 {
1029     assert(ch->unloaded());
1030     assert(!ch->isDestroyed());
1031     testInvariant();
1032
1033     // TODO: have this done by DisplayObject::unload() instead ?
1034     int oldDepth = ch->get_depth();
1035     int newDepth = DisplayObject::removedDepthOffset - oldDepth;
1036     ch->set_depth(newDepth);
1037
1038     // TODO: optimize this by searching from the end(lowest depth).
1039     container_type::iterator it =
1040         std::find_if(_charsByDepth.begin(), _charsByDepth.end(),
1041                 DepthGreaterOrEqual(newDepth));
1042
1043     _charsByDepth.insert(it, ch);
1044
1045     testInvariant();
1046 }
1047
1048 void
1049 DisplayList::removeUnloaded()
1050 {
1051     testInvariant();
1052
1053     _charsByDepth.remove_if(boost::mem_fn(&DisplayObject::unloaded));
1054
1055     testInvariant();
1056 }
1057
1058 bool
1059 DisplayList::isSorted() const
1060 {
1061     if (_charsByDepth.empty()) return true;
1062     return std::adjacent_find(_charsByDepth.begin(), _charsByDepth.end(),
1063             DepthGreaterThan()) == _charsByDepth.end();
1064 }
1065
1066
1067 #if GNASH_PARANOIA_LEVEL > 1 && !defined(NDEBUG)
1068 DisplayList::const_iterator
1069 DisplayList::nonRemoved() const
1070 {
1071     return beginNonRemoved(_charsByDepth);
1072 }
1073 #endif
1074
1075 namespace {
1076
1077 DisplayList::iterator
1078 beginNonRemoved(DisplayList::container_type& c)
1079 {
1080     const int depth = DisplayObject::removedDepthOffset -
1081         DisplayObject::staticDepthOffset;
1082
1083     return std::find_if(c.begin(), c.end(), DepthGreaterOrEqual(depth));
1084 }
1085
1086 DisplayList::const_iterator
1087 beginNonRemoved(const DisplayList::container_type& c)
1088 {
1089     const int depth = DisplayObject::removedDepthOffset -
1090         DisplayObject::staticDepthOffset;
1091
1092     return std::find_if(c.begin(), c.end(), DepthGreaterOrEqual(depth));
1093 }
1094
1095 DisplayList::iterator
1096 dlistTagsEffectiveZoneEnd(DisplayList::container_type& c)
1097 {
1098     return std::find_if(c.begin(), c.end(),
1099              DepthGreaterOrEqual(0xffff + DisplayObject::staticDepthOffset));
1100 }
1101
1102 DisplayList::const_iterator
1103 dlistTagsEffectiveZoneEnd(const DisplayList::container_type& c)
1104 {
1105     return std::find_if(c.begin(), c.end(),
1106              DepthGreaterOrEqual(0xffff + DisplayObject::staticDepthOffset));
1107 }
1108
1109 } // anonymous namespace
1110
1111
1112 std::ostream&
1113 operator<< (std::ostream& os, const DisplayList& dl)
1114 {
1115     os << "By depth: ";
1116
1117     if ( dl._charsByDepth.empty() ) return os;
1118
1119     string_table& st = getStringTable(*getObject(dl._charsByDepth.front()));
1120     ObjectURI::Logger l(st);
1121
1122     for (DisplayList::const_iterator it = dl._charsByDepth.begin(),
1123             itEnd = dl._charsByDepth.end(); it != itEnd; ++it) {
1124
1125         const DisplayObject* item = *it;
1126         if (it != dl._charsByDepth.begin()) os << " | ";
1127         os << " name:" << l.debug(item->get_name())
1128            << " depth:" << item->get_depth();
1129     }
1130
1131     return os;
1132 }
1133
1134 } // namespace gnash
1135
1136
1137 // Local Variables:
1138 // mode: C++
1139 // indent-tabs-mode: t
1140 // End: