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