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, string_table::key name, bool caseless)
 110         :
 111         _st(st),
 112         _caseless(caseless),
 113         _name(caseless ? _st.noCase(name) : name)
 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         const string_table::key itname =
 127             _caseless ? _st.noCase(item->get_name()) : item->get_name();
 128
 129         return itname == _name;
 130
 131     }
 132
 133 private:
 134     string_table& _st;
 135     const bool _caseless;
 136     const string_table::key _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, string_table::key name,
 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, name, 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     int num=0;
 720     for (const_iterator it = _charsByDepth.begin(),
 721             endIt = _charsByDepth.end(); it != endIt; ++it) {
 722
 723         const DisplayObject* dobj = *it;
 724         log_debug(_("Item %d(%s) at depth %d (char name %s, type %s)"
 725                     "Destroyed: %s, unloaded: %s"),
 726             num, dobj, dobj->get_depth(), dobj->get_name(), typeName(*dobj),
 727             dobj->isDestroyed(), dobj->unloaded());
 728         num++;
 729     }
 730 }
 731
 732
 733 void
 734 DisplayList::add_invalidated_bounds(InvalidatedRanges& ranges, bool force)
 735 {
 736     testInvariant();
 737
 738     // This function generally has nothing else to do than calling the
 739     // add_invalidated_bounds() function of all items in the display list.
 740     // However, special optimization is included for masks, which makes it
 741     // look a bit more complicated. We want to avoid that a masked DisplayObject
 742     // invalidates an area where the DisplayObject is invisible because of it's
 743     // mask (which is quite common). For example, think of a large bitmap that
 744     // covers the entire stage and is masked by a very small circle in the
 745     // middle of the stage (ie. it's only visible there). Changes in the
 746     // bitmap sprite would invalidate the whole stage even if only the small
 747     // masked portion in the middle really needs to be drawn again.
 748     //
 749     // So, like display(), we keep a stack of masks. Instead of drawing the
 750     // mask we keep a separate list of InvalidatedRanges for the masks which
 751     // later are intersected with the masked DisplayObjects' InvalidatedRanges.
 752     //
 753     // The code is much based on the display() function, so some references
 754     // in comments have been added for convenience.
 755     //
 756     // For a simpler implementation (that doesn't care about masks, but
 757     // still produces correct results) see CVS revision 1.96
 758
 759     // TODO: review this function to take "dynamic" mask and maskees
 760     // into account
 761
 762     std::stack<int> clipDepthStack; // same method used in display()
 763     std::stack<InvalidatedRanges> rangesStack;
 764     bool drawing_mask = false;
 765
 766     iterator it = beginNonRemoved(_charsByDepth);
 767     for (iterator endIt = _charsByDepth.end(); it != endIt; ++it) {
 768         DisplayObject* dobj = *it;
 769
 770 #ifndef GNASH_USE_GC
 771         assert(dobj->get_ref_count() > 0);
 772 #endif // ndef GNASH_USE_GC
 773
 774
 775         const int depth = dobj->get_depth();
 776
 777         // Discard useless masks
 778         while (!clipDepthStack.empty() && (depth > clipDepthStack.top())) {
 779             clipDepthStack.pop();
 780             rangesStack.pop();    // disable_mask() equivalent
 781
 782         }
 783
 784         // Push a new mask to the masks stack
 785         if (dobj->isMaskLayer()) {
 786
 787             const int clipDepth = dobj->get_clip_depth();
 788             clipDepthStack.push(clipDepth);
 789
 790             drawing_mask = true; // begin_submit_mask equivalent
 791
 792             if (rangesStack.empty()) {
 793                 InvalidatedRanges item;
 794                 rangesStack.push(item);
 795             }
 796             else {
 797                 // copy the top mask
 798                 rangesStack.push(rangesStack.top());
 799             }
 800         }
 801
 802         if (drawing_mask) {
 803
 804             // --> The child is part of a mask, so add ranges to our
 805             // mask ranges stack
 806
 807             assert(!rangesStack.empty());
 808             dobj->add_invalidated_bounds(rangesStack.top(), true);
 809
 810             // need to call add_invalidated_bounds again because the previous
 811             // call needs force==true. Changes to the mask itself may also
 812             // require re-rendering of the mask area, so we have to
 813             // add the mask itself to the global ranges, but this time
 814             // with normal "force" value...
 815             // As long the mask has not been invalidated and force==false this
 816             // call won't modify the "ranges" list.
 817             dobj->add_invalidated_bounds(ranges, force);
 818
 819         }
 820         else {
 821
 822             if (rangesStack.empty()) {
 823
 824                 // --> normal case for unmasked DisplayObjects
 825                 dobj->add_invalidated_bounds(ranges, force);
 826
 827             }
 828             else {
 829
 830                 // --> DisplayObject is masked, so intersect with "mask"
 831
 832                 // first get the ranges of the child in a separate list
 833                 InvalidatedRanges childRanges;
 834                 childRanges.inheritConfig(ranges);
 835
 836                 dobj->add_invalidated_bounds(childRanges, force);
 837
 838                 // then intersect ranges with topmost "mask"
 839                 childRanges.intersect(rangesStack.top());
 840
 841                 // add result to the global ranges
 842                 ranges.add(childRanges);
 843
 844             }
 845
 846         } // not drawing mask
 847
 848         // <== end of display() equivalent
 849
 850
 851         // Mask "drawing" has finished
 852         if (dobj->isMaskLayer()) {
 853             // end_submit_mask equivalent
 854             drawing_mask = false;
 855         }
 856     }
 857
 858
 859 }
 860
 861 void
 862 DisplayList::sort()
 863 {
 864     _charsByDepth.sort(DepthLessThan());
 865 }
 866
 867 void
 868 DisplayList::mergeDisplayList(DisplayList & newList)
 869 {
 870     testInvariant();
 871
 872     iterator itOld = beginNonRemoved(_charsByDepth);
 873     iterator itNew = beginNonRemoved(newList._charsByDepth);
 874
 875     iterator itOldEnd = dlistTagsEffectiveZoneEnd(_charsByDepth);
 876     iterator itNewEnd = newList._charsByDepth.end();
 877     assert(itNewEnd == dlistTagsEffectiveZoneEnd(newList._charsByDepth) );
 878
 879     // step1.
 880     // starting scanning both lists.
 881     while (itOld != itOldEnd)
 882     {
 883         iterator itOldBackup = itOld;
 884
 885         DisplayObject* chOld = *itOldBackup;
 886         int depthOld = chOld->get_depth();
 887
 888         while (itNew != itNewEnd) {
 889             iterator itNewBackup = itNew;
 890
 891             DisplayObject* chNew = *itNewBackup;
 892             int depthNew = chNew->get_depth();
 893
 894             // depth in old list is occupied, and empty in new list.
 895             if (depthOld < depthNew) {
 896
 897                 itOld++;
 898                 // unload the DisplayObject if it's in static zone(-16384,0)
 899                 if (depthOld < 0) {
 900                     _charsByDepth.erase(itOldBackup);
 901
 902                      if (chOld->unload()) reinsertRemovedCharacter(chOld);
 903                      else chOld->destroy();
 904                 }
 905
 906                 break;
 907             }
 908             // depth is occupied in both lists
 909
 910             if (depthOld == depthNew) {
 911                 ++itOld;
 912                 ++itNew;
 913
 914                 bool is_ratio_compatible =
 915                     (chOld->get_ratio() == chNew->get_ratio());
 916
 917                 if (!is_ratio_compatible || chOld->isDynamic() ||
 918                         !isReferenceable(*chOld)) {
 919                     // replace the DisplayObject in old list with
 920                     // corresponding DisplayObject in new list
 921                     _charsByDepth.insert(itOldBackup, *itNewBackup);
 922                     _charsByDepth.erase(itOldBackup);
 923
 924                     // unload the old DisplayObject
 925                     if (chOld->unload()) reinsertRemovedCharacter(chOld);
 926                     else chOld->destroy();
 927                 }
 928                 else {
 929                     newList._charsByDepth.erase(itNewBackup);
 930
 931                     // replace the transformation SWFMatrix if the old
 932                     // DisplayObject accepts static transformation.
 933                     if (chOld->get_accept_anim_moves()) {
 934                         chOld->setMatrix(getMatrix(*chNew), true);
 935                         chOld->setCxForm(getCxForm(*chNew));
 936                     }
 937                     chNew->unload();
 938                     chNew->destroy();
 939                 }
 940
 941                 break;
 942             }
 943
 944             // depth in old list is empty, but occupied in new list.
 945             ++ itNew;
 946             // add the new DisplayObject to the old list.
 947             _charsByDepth.insert(itOldBackup, *itNewBackup );
 948         }
 949
 950         // break if finish scanning the new list
 951         if (itNew == itNewEnd) break;
 952     }
 953
 954     // step2(only required if scanning of new list finished earlier in step1).
 955     // continue to scan the static zone of the old list.
 956     // unload remaining DisplayObjects directly.
 957     while((itOld != itOldEnd) && ((*itOld)->get_depth() < 0)) {
 958
 959         DisplayObject* chOld = *itOld;
 960         itOld = _charsByDepth.erase(itOld);
 961
 962         if (chOld->unload()) reinsertRemovedCharacter(chOld);
 963         else chOld->destroy();
 964     }
 965
 966     // step3(only required if scanning of old list finished earlier in step1).
 967     // continue to scan the new list.
 968     // add remaining DisplayObjects directly.
 969     if (itNew != itNewEnd) _charsByDepth.insert(itOld, itNew, itNewEnd);
 970
 971     // step4.
 972     // Copy all unloaded DisplayObjects from the new display list to the
 973     // old display list, and clear the new display list
 974     for (itNew = newList._charsByDepth.begin(); itNew != itNewEnd; ++itNew) {
 975
 976         DisplayObject* chNew = *itNew;
 977         int depthNew = chNew->get_depth();
 978
 979         if (chNew->unloaded()) {
 980             iterator it =
 981                 std::find_if(_charsByDepth.begin(), _charsByDepth.end(),
 982                     DepthGreaterOrEqual(depthNew));
 983
 984             _charsByDepth.insert(it, *itNew);
 985         }
 986     }
 987
 988     // clear the new display list after merge
 989     // ASSERT:
 990     //     - Any element in newList._charsByDepth is either marked as unloaded
 991     //    or found in this list
 992 #if GNASH_PARANOIA_LEVEL > 1
 993     for (iterator i = newList._charsByDepth.begin(),
 994             e = newList._charsByDepth.end(); i != e; ++i) {
 995
 996         DisplayObject* ch = *i;
 997         if (!ch->unloaded()) {
 998
 999             iterator found =
1000                 std::find(_charsByDepth.begin(), _charsByDepth.end(), ch);
1001
1002             if (found == _charsByDepth.end())
1003             {
1004                 log_error("mergeDisplayList: DisplayObject %s (%s at depth "
1005                         "%d [%d]) about to be discarded in given display list"
1006                         " is not marked as unloaded and not found in the"
1007                         " merged current displaylist",
1008                         ch->getTarget(), typeName(*ch), ch->get_depth(),
1009                         ch->get_depth()-DisplayObject::staticDepthOffset);
1010                 std::abort();
1011             }
1012         }
1013     }
1014 #endif
1015     newList._charsByDepth.clear();
1016
1017     testInvariant();
1018 }
1019
1020
1021 void
1022 DisplayList::reinsertRemovedCharacter(DisplayObject* ch)
1023 {
1024     assert(ch->unloaded());
1025     assert(!ch->isDestroyed());
1026     testInvariant();
1027
1028     // TODO: have this done by DisplayObject::unload() instead ?
1029     int oldDepth = ch->get_depth();
1030     int newDepth = DisplayObject::removedDepthOffset - oldDepth;
1031     ch->set_depth(newDepth);
1032
1033     // TODO: optimize this by searching from the end(lowest depth).
1034     container_type::iterator it =
1035         std::find_if(_charsByDepth.begin(), _charsByDepth.end(),
1036                 DepthGreaterOrEqual(newDepth));
1037
1038     _charsByDepth.insert(it, ch);
1039
1040     testInvariant();
1041 }
1042
1043 void
1044 DisplayList::removeUnloaded()
1045 {
1046     testInvariant();
1047
1048     _charsByDepth.remove_if(boost::mem_fn(&DisplayObject::unloaded));
1049
1050     testInvariant();
1051 }
1052
1053 bool
1054 DisplayList::isSorted() const
1055 {
1056     if (_charsByDepth.empty()) return true;
1057     return std::adjacent_find(_charsByDepth.begin(), _charsByDepth.end(),
1058             DepthGreaterThan()) == _charsByDepth.end();
1059 }
1060
1061
1062 #if GNASH_PARANOIA_LEVEL > 1 && !defined(NDEBUG)
1063 DisplayList::const_iterator
1064 DisplayList::nonRemoved() const
1065 {
1066     return beginNonRemoved(_charsByDepth);
1067 }
1068 #endif
1069
1070 namespace {
1071
1072 DisplayList::iterator
1073 beginNonRemoved(DisplayList::container_type& c)
1074 {
1075     const int depth = DisplayObject::removedDepthOffset -
1076         DisplayObject::staticDepthOffset;
1077
1078     return std::find_if(c.begin(), c.end(), DepthGreaterOrEqual(depth));
1079 }
1080
1081 DisplayList::const_iterator
1082 beginNonRemoved(const DisplayList::container_type& c)
1083 {
1084     const int depth = DisplayObject::removedDepthOffset -
1085         DisplayObject::staticDepthOffset;
1086
1087     return std::find_if(c.begin(), c.end(), DepthGreaterOrEqual(depth));
1088 }
1089
1090 DisplayList::iterator
1091 dlistTagsEffectiveZoneEnd(DisplayList::container_type& c)
1092 {
1093     return std::find_if(c.begin(), c.end(),
1094              DepthGreaterOrEqual(0xffff + DisplayObject::staticDepthOffset));
1095 }
1096
1097 DisplayList::const_iterator
1098 dlistTagsEffectiveZoneEnd(const DisplayList::container_type& c)
1099 {
1100     return std::find_if(c.begin(), c.end(),
1101              DepthGreaterOrEqual(0xffff + DisplayObject::staticDepthOffset));
1102 }
1103
1104 } // anonymous namespace
1105
1106
1107 std::ostream&
1108 operator<< (std::ostream& os, const DisplayList& dl)
1109 {
1110     os << "By depth: ";
1111     for (DisplayList::const_iterator it = dl._charsByDepth.begin(),
1112             itEnd = dl._charsByDepth.end(); it != itEnd; ++it) {
1113
1114         const DisplayObject* item = *it;
1115         if (it != dl._charsByDepth.begin()) os << " | ";
1116         os << " name:" << item->get_name()
1117            << " depth:" << item->get_depth();
1118     }
1119
1120     return os;
1121 }
1122
1123 } // namespace gnash
1124
1125
1126 // Local Variables:
1127 // mode: C++
1128 // indent-tabs-mode: t
1129 // End: