libcore/DisplayList.cpp

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