placement-index.cpp

Go to the documentation of this file.

/*
  PlacementIndex  -  tracking individual Placements and their relations

  Copyright (C)         Lumiera.org
    2008,               Hermann Vosseler <Ichthyostega@web.de>

  This program is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 2 of
  the License, or (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

* *****************************************************/


#include "steam/mobject/session/placement-index.hpp"
#include "steam/mobject/session/session-impl.hpp"
#include "steam/mobject/session/scope.hpp"
#include "lib/typed-allocation-manager.hpp"
#include "lib/iter-adapter-stl.hpp"
#include "lib/util-foreach.hpp"
#include "lib/iter-source.hpp"
#include "include/logging.h"

#include <boost/functional/hash.hpp>
#include <unordered_map>
#include <functional>
#include <memory>
#include <string>

namespace lumiera {
namespace error {
  LUMIERA_ERROR_DEFINE (NOT_IN_SESSION, "referring to a Placement not known to the current session");
  LUMIERA_ERROR_DEFINE (PLACEMENT_TYPE, "requested Placement (pointee) type not compatible with data or context");
  LUMIERA_ERROR_DEFINE (NONEMPTY_SCOPE, "Placement scope (still) contains other elements");
}}

namespace steam {
namespace mobject {
namespace session {
  
  using boost::hash;
  using std::shared_ptr;
  using std::unordered_map;
  using std::unordered_multimap;
  using lib::TypedAllocationManager;
  using lib::iter_stl::IterSnapshot;
  using lib::iter_stl::eachVal;
  using lib::iter_source::eachMapKey;
  using lib::iter_source::eachDistinctKey;
  using lib::iter_source::eachValForKey;
  using std::placeholders::_1;
  using std::function;
  using std::bind;
  using std::make_pair;
  using std::pair;
  
  using util::for_each;
  using util::has_any;
  
  
  
  
  /* some type shorthands */
  typedef mobject::PlacementMO PlacementMO;
  typedef PlacementIndex::PRef PRef;
  typedef PlacementIndex::ID ID;
  
  
  /*****************************************************************/
  class PlacementIndex::Table
    {
      typedef shared_ptr<PlacementMO> PPlacement;
      
      struct PlacementEntry
        {
          PPlacement element;
          PPlacement scope;
        };
      
      // using hashtables to implement the index
      typedef PlacementMO::ID PID;
      typedef unordered_map<PID, PlacementEntry>  IDTable;
      typedef std::unordered_multimap<PID,PID> ScopeTable;
      
      typedef pair<ScopeIter, ScopeIter> ScopeContents;
      
      
      TypedAllocationManager allocator_;
      IDTable placementTab_;
      ScopeTable scopeTab_;
      
      PPlacement root_;
      
    public:
      Table()
        { }
      
     ~Table()
        try {
            root_.reset();
            clear();
          }
        catch (lumiera::Error& err)
          {
            WARN (session, "Problem while purging PlacementIndex: %s", err.what());
            lumiera_error(); // discard any error state
          }
      
      
      size_t
      size()  const            
        {
          return placementTab_.size();
        }
      
      size_t
      scope_cnt()  const       
        {
          return scopeTab_.size();
        }
      
      size_t
      element_cnt()  const
        {
          return allocator_.numSlots<PlacementMO>();
        }
      
      bool
      contains (ID id)  const
        {
          return util::contains(placementTab_, id);
        }
      
      
      PlacementMO&
      fetch (ID id)  const
        {
          REQUIRE (contains (id));
          PPlacement const& entry = base_entry(id).element;
          
          ENSURE (entry);
          ENSURE (id == entry->getID());
          return *entry;
        }
      
      PlacementMO&
      fetchScope (ID id)  const
        {
          REQUIRE (contains (id));
          PPlacement const& scope = base_entry(id).scope;
          
          ENSURE (scope);
          ENSURE (contains (scope->getID()));
          return *scope;
        }
      
      PlacementIndex::iterator
      queryScopeContents (ID id)  const
        {
          REQUIRE (contains (id));
          ScopeContents contents = scopeTab_.equal_range (id);
          return iterator (ScopeRangeIter(contents.first, contents.second)
                          ,scopeIndexElementsResolver() );
        }
      
      
      
      void
      clear()
        {
          INFO (session, "Purging Placement Tables...");
          scopeTab_.clear();
          placementTab_.clear();
          
          if (root_)
            setupRoot (*root_);
        }
      
      
      void
      setupRoot (PlacementMO const& rootDef)
        {
          REQUIRE (0 == placementTab_.size());
          REQUIRE (0 == scopeTab_.size());
          
          root_ = allocator_.create<PlacementMO> (rootDef);
          ID rootID = root_->getID();
          placementTab_[rootID].element = root_;
          placementTab_[rootID].scope   = root_;
          
          ENSURE (contains (rootID));
          ENSURE (scopeTab_.empty());
          ENSURE (1 == size());
        }
      
      PlacementMO&
      getRootElement()
        {
          REQUIRE (root_);
          REQUIRE (0 < size());
          REQUIRE (contains (root_->getID()));
          
          return *root_;
        }
      
      
      ID
      addEntry (PlacementMO const& newObj, ID scopeID)
        {
          REQUIRE (contains (scopeID));
          
          PPlacement newEntry = allocator_.create<PlacementMO> (newObj);
          ID newID = newEntry->getID();
          
          ASSERT (newID, "invalid");
          ASSERT (!contains (newID));
          placementTab_[newID].element = newEntry;
          placementTab_[newID].scope   = placementTab_[scopeID].element;
          scopeTab_.insert (make_pair (scopeID, newID));
          return newID;
        }
      
      bool
      removeEntry (ID id)
        {
          if (!contains (id))
            {
              ENSURE (!util::contains(scopeTab_, id));
              return false;
            }
          
          if (util::contains(scopeTab_, id))
            throw error::State{"Unable to remove the specified Placement, "
                               "because it defines an non-empty scope. "
                               "You need to delete any contents first."
                              , LERR_(NONEMPTY_SCOPE)};              
          
          ASSERT (contains (id));
          PlacementEntry toRemove = remove_base_entry (id);
          remove_from_scope (toRemove.scope->getID(), id);
          ENSURE (!util::contains(scopeTab_, id));
          ENSURE (!contains (id));
          return true;
        }
      
      void
      removeAll (ID scopeID)
        {
          remove_all_from_scope (scopeID); // recursive
          removeEntry (scopeID);          //  discard top-level
          
          ENSURE (!util::contains(scopeTab_, scopeID));
          ENSURE (!contains (scopeID));
        }
      
      
      /* == access for self-test == */
      
      using IDIter = lib::IterSource<PID>::iterator;
      
      PlacementMO* _root_4check ()        { return root_.get();                 }
      PlacementMO* _element_4check (ID id){ return base_entry(id).element.get();}
      PlacementMO* _scope_4check (ID id)  { return base_entry(id).scope.get();  }
      IDIter       _eachEntry_4check ()   { return eachMapKey (placementTab_);  }
      IDIter       _eachScope_4check ()   { return eachDistinctKey (scopeTab_); }
      IDIter       _contents_4check(ID id){ return eachValForKey (scopeTab_,id);}
      
      
    private:
      typedef IDTable::const_iterator Slot;
      
      PlacementEntry const&
      base_entry (ID key)  const
        {
          Slot pos = placementTab_.find (key);
          if (pos == placementTab_.end())
            throw error::Logic("lost a Placement expected to be registered within PlacementIndex.");
          
          return pos->second;
        }
      
      PlacementEntry
      remove_base_entry (ID key)
        {
          Slot pos = placementTab_.find (key);
          REQUIRE (pos != placementTab_.end());
          PlacementEntry dataToRemove (pos->second);
          placementTab_.erase(pos);
          return dataToRemove;
        }
      
      void
      remove_from_scope (ID scopeID, ID entryID)
        {
          typedef ScopeTable::const_iterator Pos;
          pair<Pos,Pos> searchRange = scopeTab_.equal_range(scopeID);
          
          Pos pos = searchRange.first;
          Pos end = searchRange.second;
          for ( ; pos!=end; ++pos)
            if (pos->second == entryID)
              {
                scopeTab_.erase(pos);
                return;
              }
          
          NOTREACHED();
        }
      
      void
      remove_all_from_scope (ID scopeID)
        {
          typedef ScopeTable::const_iterator Pos;
          pair<Pos,Pos> scopeEntries = scopeTab_.equal_range(scopeID);
          Pos first = scopeEntries.first;
          Pos end   = scopeEntries.second;
          
          // take a snapshot of all children to be processed recursively
          typedef IterSnapshot<PID> ChildIDs;
          ChildIDs child (eachVal(first,end));
          
          scopeTab_.erase (first,end); // assumed to be NOP for first==end
          
          for ( ; child; ++child )
            {
              remove_all_from_scope (*child); // recursive
              remove_base_entry (*child);    //  discard storage
              
              ENSURE (!util::contains(scopeTab_, *child));
              ENSURE (!contains (*child));
            }
        }
      
      
      
      PlacementMO&
      resolveScopeIndexElement(pair<PID,PID> const& entry)  const
        {
          ID elemID (entry.second);
          ASSERT (contains (elemID));
          return fetch (elemID);
        }
      
      
      typedef function<PlacementMO& (pair<PID,PID> const&)> ElementResolver;
      mutable ElementResolver elementResolver_;
      
      ElementResolver
      scopeIndexElementsResolver()  const  
        {
          if (!elementResolver_)
            elementResolver_ = bind (&Table::resolveScopeIndexElement, this, _1 );
          return elementResolver_;
        }
    };
   //(End) placement index table implementation
  
  
  
  
  
  
  
  /* ============ PlacementIndex implementation functions ============ */
  
  
  PlacementIndex::PlacementIndex (PlacementMO const& rootDef)
    : pTab_(new Table)
    {
      INFO (session, "Initialising PlacementIndex...");
      
      pTab_->setupRoot(rootDef);
      ENSURE (isValid());
    }
  
  PlacementIndex::~PlacementIndex() { }
  
  
  PlacementMO&
  PlacementIndex::getRoot()  const
  {
    return pTab_->getRootElement();
  }
  
  
  size_t
  PlacementIndex::size()  const
  {
    ASSERT (0 < pTab_->size());
    return pTab_->size() - 1;  // root not counted
  }
  
  
  bool
  PlacementIndex::contains (ID id)  const
  {
    return pTab_->contains (id);
  }
  
  
  PlacementMO&
  PlacementIndex::find (ID id)  const
  {
    __check_knownID(*this,id);
    return pTab_->fetch (id);
  }
  
  
  
  PlacementMO&
  PlacementIndex::getScope (ID id)  const
  {
    __check_knownID(*this,id);
    return pTab_->fetchScope (id);
  }
  
  
  PlacementIndex::iterator
  PlacementIndex::getReferrers (ID id)  const
  {
    __check_knownID(*this, id);
    return pTab_->queryScopeContents(id);
  }
  
  
  ID
  PlacementIndex::insert (PlacementMO const& newObj, ID targetScope)
  {
    if (!contains (targetScope))
      throw error::Logic ("Specified a non-registered Placement as scope "
                          "while adding another Placement to the index"
                         ,LERR_(INVALID_SCOPE));                          
      
    return pTab_->addEntry(newObj, targetScope);
  }
  
  
  bool
  PlacementIndex::remove (ID id)
  {
    if (id == getRoot().getID())
      throw error::Fatal ("Request to kill the model root.");
    
    return pTab_->removeEntry (id);
  }
  
  
  void
  PlacementIndex::clear (ID targetScope)
  {
    if (targetScope == getRoot().getID())
      pTab_->clear();
    else
      pTab_->removeAll (targetScope);
    
    ENSURE (isValid());
  }
  
  
  void
  PlacementIndex::clear()
  {
    pTab_->clear();
  }
  
  
  
  
  
  /* ====== PlacementIndex validity self-check ====== */
  
  namespace { // self-check implementation helpers...
    
    LUMIERA_ERROR_DEFINE(INDEX_CORRUPTED, "PlacementIndex corrupted");
    
    struct SelfCheckFailure
      : error::Fatal
      {
        SelfCheckFailure (lib::Literal currentTest, string failure)
          : error::Fatal (string("Failed test: ")+currentTest+ " : "+failure
                         ,LUMIERA_ERROR_INDEX_CORRUPTED)
          { }
      };
  }
  
  
  class PlacementIndex::Validator
    {
      
      PlacementIndex::Table& tab;
      
      PlacementMO* elm (ID id) { return tab._element_4check (id);}
      PlacementMO* sco (ID id) { return tab._scope_4check (id);  }
      
      
      
#define VERIFY(_CHECK_, CHECK_ID, DESCRIPTION) \
      if (!(_CHECK_))                           \
        throw SelfCheckFailure (CHECK_ID, (DESCRIPTION));
      
      
      void
      checkRoot (PMO* root)
        {
          VERIFY ( root,                 "(0.1) Basics",   "Root element missing");
          VERIFY ( root->isValid(),      "(0.2) Basics",   "Root Placement invalid");
          VERIFY ( (*root)->isValid(),   "(0.3) Basics",   "Root MObject self-check failure");
        }
      
      void
      checkEntry (ID id)
        {
          VERIFY ( tab.contains(id),     "(1.1) Elements", "PlacementIndex main table corrupted");
          VERIFY ( elm(id),              "(1.2) Elements", "Entry doesn't hold a Placement");
          VERIFY ( id==elm(id)->getID(), "(1.3) Elements", "Element stored with wrong ID");      
          VERIFY ( elm(id)->isValid(),   "(1.4) Elements", "Index contains invalid Placement")
          VERIFY ( sco(id),              "(1.5) Elements", "Entry has undefined scope");
          VERIFY ( sco(id)->isValid(),   "(1.6) Elements", "Entry has invalid scope");
          VERIFY ( tab.contains (sco(id)->getID()),
                                         "(1.7) Elements", "Element associated with an unknown scope");
          
          PMO& theElement = *elm(id);
          ID theScope (sco(id)->getID());
          if (theScope == id
             && elm(id)==tab._root_4check()
             )        // no need to check root,
            return;  //  because root is it's own scope
          
          iterator elementsInScope = tab.queryScopeContents(theScope);
          auto equalsTheElement   = [&](PMO& entry) { return entry == theElement; };
          bool properlyRegistered = has_any (elementsInScope, equalsTheElement);
          
          VERIFY ( properlyRegistered,   "(1.8) Elements", "Element not registered as member of the enclosing scope: "+ theElement);
        }
      
      void
      checkScope (ID id)
        {
          VERIFY ( tab.contains(id),     "(2.1) Scopes",   "Scope not registered in main table");
          VERIFY ( elm(id),              "(2.2) Scopes",   "Scope entry doesn't hold a Placement");
          VERIFY ( sco(id),              "(2.3) Scopes",   "Scope entry doesn't hold a containing Scope");
          
          PMO* root  = tab._root_4check();
          PMO* scope = sco(id);
          while (scope && scope != sco(scope->getID()))
            scope = sco(scope->getID());
          
          VERIFY ( root==scope,          "(2.4) Scopes",   "Found a scope not attached below root.");
          
          for_each ( tab._contents_4check(id), &Validator::checkScopeEntry, this, id, _1 );
        }
      
      void
      checkScopeEntry (ID scope, ID entry)
        {
          VERIFY ( tab.contains(entry),  "(2.5) Scopes",   "Scope member not registered in main table");
          VERIFY ( elm(entry),           "(2.6) Scopes",   "Scope member entry doesn't refer to a valid Placement");
          VERIFY ( sco(entry),           "(2.7) Scopes",   "Scope member entry is lacking valid scope information");
          VERIFY ( sco(entry)->getID() == scope,
                                         "(2.8) Scopes",   "Scope member registered as belonging to a different scope in main table");
        }
      
      void
      checkAllocation ()
        {
          VERIFY ( 0 < tab.size(),       "(4.1) Storage",  "Implementation table is empty");
          VERIFY ( 0 < tab.element_cnt(),"(4.2) Storage",  "No Placement instances allocated");
          VERIFY ( tab.size()==tab.scope_cnt()+1,
                                         "(4.3) Storage",  "Number of elements and scope entries disagree");
          VERIFY ( tab.size()==tab.element_cnt(),
                                         "(4.4) Storage",  "Number of entries doesn't match number of allocated Placement instances");
        }
      
      
      public:
        Validator (Table& indexTable)
          : tab(indexTable)
          {
            checkRoot (tab._root_4check());
            
            for_each ( tab._eachEntry_4check(), &Validator::checkEntry, this, _1 );
            for_each ( tab._eachScope_4check(), &Validator::checkScope, this, _1 );
            
            checkAllocation();
          }
      
    };//(End) Validator (PlacementIndex self-check implementation)
  
  
  
  
  

  bool
  PlacementIndex::isValid()  const
  {
    try
      {
        VERIFY ( pTab_, "(0) Basics" ,"Implementation tables not initialised");
        
        Validator verify(*pTab_);
        return true;
      }
    
    catch(SelfCheckFailure& failure)
      {
        lumiera_error();
        ERROR (session, "%s", failure.what());
      }
    return false;
  }
  
#undef VERIFY
  
  
  
}}} // namespace steam::mobject::session