libcore/DisplayList.cpp

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