source/environment.cc

   1 /* This file is part of Shapes.
   2  *
   3  * Shapes is free software: you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation, either version 3 of the License, or
   6  * any later version.
   7  *
   8  * Shapes is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with Shapes.  If not, see <http://www.gnu.org/licenses/>.
  15  *
  16  * Copyright 2008, 2013, 2014 Henrik Tidefelt
  17  */
  18
  19 #include <cmath>
  20 #include <iomanip>
  21
  22 #include "environment.h"
  23 #include "shapesexceptions.h"
  24 #include "shapescore.h"
  25 #include "consts.h"
  26 #include "globals.h"
  27 #include "shapesvalue.h"
  28 #include "classtypes.h"
  29 #include "hottypes.h"
  30 #include "continuations.h"
  31 #include "statetypes.h"
  32 #include "multipage.h"
  33 #include "errorhandlers.h"
  34 #include "debuglog.h"
  35 #include "check.h"
  36
  37 using namespace Shapes;
  38
  39
  40 size_t Kernel::Environment::createdCount = 0;
  41 size_t Kernel::Environment::liveCount = 0;
  42 Kernel::Environment::LexicalKey Kernel::Environment::theMissingKey( 0, std::numeric_limits< size_t >::max( ) );
  43 const Ast::SourceLocation Kernel::Environment::THE_INITIALIZATION_LOCATION( Ast::FileID::build_internal( "< Initialization >" ) );
  44 template< class T >
  45 class Binary
  46 {
  47 public:
  48   T val;
  49   Binary( const T & _val ) : val( _val ) { }
  50 };
  51
  52 template< class T >
  53 std::ostream &
  54 operator << ( std::ostream & os, const Binary< T > & self )
  55 {
  56   for( int i = 8*sizeof( T ) - 1; i >= 0; --i )
  57     {
  58       if( (( self.val & (T(1)<<i) )) != 0 )
  59         {
  60           os << 1 ;
  61         }
  62       else
  63         {
  64           os << '_' ;
  65         }
  66     }
  67   return os;
  68 }
  69
  70
  71
  72 Kernel::Thunk::Thunk( Kernel::PassedEnv env, Kernel::PassedDyn dyn, Ast::Expression * expr )
  73   : env_( env ), dyn_( dyn ), expr_( expr ), forced_( false )
  74 { }
  75
  76 void
  77 Kernel::Thunk::force( Kernel::EvalState * evalState, bool onlyOnce ) const
  78 {
  79   if( onlyOnce )
  80     {
  81       if( forced_ )
  82         {
  83           throw Exceptions::InternalError( "It's unwise to force a thunk twice!  It should be deleted right after the first force." );
  84         }
  85       forced_ = true;
  86     }
  87
  88   evalState->expr_ = expr_;
  89   evalState->env_ = env_;
  90   evalState->dyn_ = dyn_;
  91
  92   /* The continuation is not se by the thunk! */
  93 }
  94
  95 Kernel::Thunk *
  96 Kernel::Thunk::deepCopy( )
  97 {
  98   return new Thunk( env_, dyn_, expr_ );
  99 }
 100
 101
 102 void
 103 Kernel::Thunk::gcMark( Kernel::GCMarkedSet & marked )
 104 {
 105   if( ! forced_ )
 106     {
 107       env_->gcMark( marked );
 108       dyn_->gcMark( marked );
 109     }
 110 }
 111
 112 Ast::Expression *
 113 Kernel::Thunk::getExpr( )
 114 {
 115   return expr_;
 116 }
 117
 118 void
 119 Kernel::Thunk::printEnv( std::ostream & os ) const
 120 {
 121   env_->print( os );
 122 }
 123
 124
 125 Kernel::Variable::Variable( const RefCountPtr< const Lang::Value > & val )
 126   : thunk_( 0 ), val_( val ), state_( Kernel::Variable::COLD )
 127 { }
 128
 129 Kernel::Variable::Variable( Kernel::Thunk * thunk )
 130   : thunk_( thunk ), val_( NullPtr< const Lang::Value >( ) ), state_( Kernel::Variable::THUNK )
 131 { }
 132
 133 Kernel::Variable::~Variable( )
 134 {
 135   if( thunk_ != NULL )
 136     {
 137       delete thunk_;
 138     }
 139 }
 140
 141 Kernel::State::State( )
 142   : alive_( true )
 143 { }
 144
 145 Kernel::State::~State( )
 146 { }
 147
 148 void
 149 Kernel::State::tackOn( Kernel::EvalState * evalState, const RefCountPtr< const Lang::Value > & piece, const Ast::SourceLocation & callLoc )
 150 {
 151   if( ! alive_ )
 152     {
 153       throw Exceptions::DeadStateAccess( );
 154     }
 155   this->tackOnImpl( evalState, piece, callLoc );
 156 }
 157
 158 void
 159 Kernel::State::peek( Kernel::EvalState * evalState, const Ast::SourceLocation & callLoc )
 160 {
 161   if( ! alive_ )
 162     {
 163       throw Exceptions::DeadStateAccess( );
 164     }
 165   this->peekImpl( evalState, callLoc );
 166 }
 167
 168 void
 169 Kernel::State::freeze( Kernel::EvalState * evalState, const Ast::SourceLocation & callLoc )
 170 {
 171   if( ! alive_ )
 172     {
 173       throw Exceptions::DeadStateAccess( );
 174     }
 175   /* It would make sense to have an intermediate state here.
 176    */
 177   alive_ = false;
 178
 179   // Perhaps, it would be smart to use a continuation to erase the implementation once it is used...
 180   //  evalState->cont_ = Kernel::ContRef( new Kernel::StmtStoreVariableContinuation( selfRef, evalState->cont_, callLoc ) );
 181
 182   this->freezeImpl( evalState, callLoc );
 183 }
 184
 185 RefCountPtr< const Lang::Function >
 186 Kernel::State::getMutator( const char * mutatorID )
 187 {
 188   return getClass( )->getMutator( mutatorID );
 189 }
 190
 191 RefCountPtr< const char >
 192 Kernel::State::getTypeName( ) const
 193 {
 194   return this->getClass( )->getPrettyName( );
 195 }
 196
 197 bool
 198 Kernel::State::isAlive( ) const
 199 {
 200   return alive_;
 201 }
 202
 203
 204 void
 205 Kernel::Variable::force( const Kernel::VariableHandle & selfRef, Kernel::EvalState * evalState ) const
 206 {
 207   /* The reason that selfRef is passed as const reference is that this is a const method, and it is expected that selfRef actually is a handle to *this.  Hence, it does not make sense to not allow the selfRef to be passed by const reference.  On the other hand, we actually do need to do some non-const things with selfRef, and therefore we resort to some ugly const_casting this time.
 208    */
 209   if( state_ == Kernel::Variable::THUNK )
 210     {
 211       state_ = Kernel::Variable::FORCING;
 212       evalState->cont_ = Kernel::ContRef( new Kernel::StoreVariableContinuation( const_cast< Kernel::VariableHandle & >( selfRef ), evalState->cont_, thunk_->getExpr( )->loc( ) ) );
 213       thunk_->force( evalState );
 214       delete thunk_;
 215       thunk_ = 0;
 216       return;
 217     }
 218   if( val_ == NullPtr< const Lang::Value >( ) )
 219     {
 220       if( state_ == Kernel::Variable::FORCING )
 221         {
 222           throw Exceptions::MiscellaneousRequirement( "Cyclic forcing." );
 223         }
 224       throw Exceptions::InternalError( "Force failed.  No value, not forcing." );
 225     }
 226   Kernel::ContRef cont = evalState->cont_;
 227   cont->takeHandle( const_cast< Kernel::VariableHandle & >( selfRef ), evalState );
 228 }
 229
 230 RefCountPtr< const Lang::Value > &
 231 Kernel::Variable::getUntyped( ) const
 232 {
 233   if( val_ == NullPtr< const Lang::Value >( ) )
 234     {
 235       throw Exceptions::InternalError( "The value is not ready to be get without continuation." );
 236     }
 237   return val_;
 238 }
 239
 240
 241 bool
 242 Kernel::Variable::isThunk( ) const
 243 {
 244   return ( state_ & Kernel::Variable::FORCING ) != 0;
 245 }
 246
 247 bool
 248 Kernel::Variable::isThunk( Ast::Expression * expr ) const
 249 {
 250   return state_ == Kernel::Variable::THUNK && thunk_->getExpr( ) == expr;
 251 }
 252
 253 Kernel::Thunk *
 254 Kernel::Variable::copyThunk( ) const
 255 {
 256   if( thunk_ == NULL )
 257     {
 258       throw Exceptions::InternalError( "Variable::copyThunk: There was no thunk to copy." );
 259     }
 260   return thunk_->deepCopy( );
 261 }
 262
 263 void
 264 Kernel::Variable::gcMark( Kernel::GCMarkedSet & marked )
 265 {
 266   if( thunk_ != NULL )
 267     {
 268       thunk_->gcMark( marked );
 269       return;
 270     }
 271   if( val_ != NullPtr< const Lang::Value >( ) )
 272     {
 273       const_cast< Lang::Value * >( val_.getPtr( ) )->gcMark( marked );
 274     }
 275 }
 276
 277 void
 278 Kernel::Variable::setValue( const RefCountPtr< const Lang::Value > & val ) const
 279 {
 280   if( state_ != Kernel::Variable::FORCING )
 281     throw Exceptions::BadSetValueState( );
 282   val_ = val;
 283   state_ = Kernel::Variable::COLD;
 284 }
 285
 286
 287 Kernel::DynamicVariableProperties::~DynamicVariableProperties( )
 288 {
 289   /* We do not own id_.
 290    */
 291 }
 292
 293 Kernel::DynamicStateProperties::~DynamicStateProperties( )
 294 {
 295   /* We do not own id_.
 296    */
 297 }
 298
 299
 300 void
 301 Kernel::Environment::initDefineHandle( const Ast::PlacedIdentifier & id, const Kernel::VariableHandle & val )
 302 {
 303   if( Interaction::logGlobals )
 304     {
 305       std::ostream & os = Kernel::theDebugLog.os( );
 306       os << "--log-globals> variable: " ;
 307       id.show( os, Ast::Identifier::VARIABLE );
 308       os << std::endl ;
 309     }
 310
 311   if( ! bindings_->insert( id, THE_INITIALIZATION_LOCATION ) )
 312     {
 313       /* An error message has already been generated. */
 314       return;
 315     }
 316   values_->push_back( val );
 317
 318   CHECK( /* Assume that matching element counts insure that the identifier is mapped to the correct position. */
 319     if( values_->size( ) != bindings_->size( ) ){
 320       throw Exceptions::InternalError( "Kernel::Environment::initDefineHandle: Inconsistent number of values." );
 321     } );
 322 }
 323
 324 void
 325 Kernel::Environment::initDefineCoreFunction( Lang::CoreFunction * fun )
 326 {
 327   initDefineHandle( fun->id( ), Kernel::VariableHandle( new Kernel::Variable( RefCountPtr< const Lang::Value >( fun ) ) ) );
 328 }
 329
 330 void
 331 Kernel::Environment::initDefineCoreFunction( RefCountPtr< const Lang::CoreFunction > fun )
 332 {
 333   initDefineHandle( fun->id( ), Kernel::VariableHandle( new Kernel::Variable( fun ) ) );
 334 }
 335
 336 void
 337 Kernel::Environment::initDefine( const Ast::PlacedIdentifier & id, const RefCountPtr< const Lang::Value > & val )
 338 {
 339   initDefineHandle( id, Kernel::VariableHandle( new Kernel::Variable( val ) ) );
 340 }
 341
 342 void
 343 Kernel::Environment::initDefine( const RefCountPtr< const Ast::NamespacePath > & ns, const char * name, const RefCountPtr< const Lang::Value > & val )
 344 {
 345   Ast::PlacedIdentifier id( ns, name);
 346   initDefineHandle( id, Kernel::VariableHandle( new Kernel::Variable( val ) ) );
 347 }
 348
 349 void
 350 Kernel::Environment::initDefine( const Ast::PlacedIdentifier & id, Kernel::StateHandle state )
 351 {
 352   if( Interaction::logGlobals )
 353     {
 354       std::ostream & os = Kernel::theDebugLog.os( );
 355       os << "--log-globals> state: " ;
 356       id.show( os, Ast::Identifier::STATE );
 357       os << std::endl ;
 358     }
 359
 360   if( ! stateBindings_->insert( id, THE_INITIALIZATION_LOCATION ) )
 361     {
 362       /* An error message has already been generated. */
 363       return;
 364     }
 365   states_->push_back( state );
 366
 367   CHECK( /* Assume that matching element counts insure that the identifier is mapped to the correct position. */
 368     if( states_->size( ) != stateBindings_->size( ) ){
 369       throw Exceptions::InternalError( "Kernel::Environment::initDefine: Inconsistent number of states." );
 370     } );
 371 }
 372
 373 void
 374 Kernel::Environment::initDefine( const RefCountPtr< const Ast::NamespacePath > & ns, const char * name, Kernel::StateHandle state )
 375 {
 376   Ast::PlacedIdentifier id( ns, name);
 377   initDefine( id, state );
 378 }
 379
 380 void
 381 Kernel::Environment::initDefineClass( const RefCountPtr< const Lang::Class > & cls )
 382 {
 383   RefCountPtr< const char > idRef = cls->getPrettyName( );
 384   const char * simpleId = strdup( idRef.getPtr( ) );
 385   charPtrDeletionList_.push_back( simpleId );
 386   initDefineHandle( Ast::PlacedIdentifier( Lang::THE_NAMESPACE_Shapes_Data_Type, simpleId ), Kernel::VariableHandle( new Kernel::Variable( cls ) ) );
 387 }
 388
 389 void
 390 Kernel::Environment::initDefineDynamic( DynamicVariableProperties * dynProps )
 391 {
 392   const Ast::PlacedIdentifier & id( dynProps->id( ) );
 393
 394   if( Interaction::logGlobals )
 395     {
 396       Kernel::theDebugLog.os( ) << "--log-globals> dynamic: " ;
 397       id.show( Kernel::theDebugLog.os( ), Ast::Identifier::DYNAMIC_VARIABLE );
 398       Kernel::theDebugLog.os( ) << std::endl ;
 399     }
 400
 401   if( ! dynamicKeyBindings_->insert( id, THE_INITIALIZATION_LOCATION ) )
 402     {
 403       /* An error message has already been generated. */
 404       return;
 405     }
 406   dynamicKeyValues_->push_back( dynProps );
 407
 408   CHECK( /* Assume that matching element counts insure that the identifier is mapped to the correct position. */
 409     if( dynamicKeyValues_->size( ) != dynamicKeyBindings_->size( ) ){
 410       throw Exceptions::InternalError( "Kernel::Environment::initDefineDynamic: Inconsistent number of dynamic keys (1 argument)." );
 411     } );
 412 }
 413
 414 void
 415 Kernel::Environment::initDefineDynamic( const Ast::PlacedIdentifier & id, const RefCountPtr< const Lang::Function > & filter, const Kernel::VariableHandle & defaultVal )
 416 {
 417   initDefineDynamic( newPlacedIdentifier( id ), filter, defaultVal );
 418 }
 419
 420 void
 421 Kernel::Environment::initDefineDynamic( const Ast::PlacedIdentifier * id, const RefCountPtr< const Lang::Function > & filter, const Kernel::VariableHandle & defaultVal )
 422 {
 423   if( Interaction::logGlobals )
 424     {
 425       Kernel::theDebugLog.os( ) << "--log-globals> dynamic: " ;
 426       id->show( Kernel::theDebugLog.os( ), Ast::Identifier::DYNAMIC_VARIABLE );
 427       Kernel::theDebugLog.os( ) << std::endl ;
 428     }
 429
 430   if( ! dynamicKeyBindings_->insert( *id, THE_INITIALIZATION_LOCATION ) )
 431     {
 432       /* An error message has already been generated. */
 433       return;
 434     }
 435   Kernel::DynamicEnvironmentKeyType key = dynamicKeyValues_->size( );
 436   dynamicKeyValues_->push_back( new Kernel::UserDynamicVariableProperties( id, key, filter, defaultVal ) );
 437
 438   CHECK( /* Assume that matching element counts insure that the identifier is mapped to the correct position. */
 439     if( dynamicKeyValues_->size( ) != dynamicKeyBindings_->size( ) ){
 440       throw Exceptions::InternalError( "Kernel::Environment::initDefineDynamic: Inconsistent number of dynamic keys (3 arguments)." );
 441     } );
 442 }
 443
 444 void
 445 Kernel::Environment::initDefineDynamicHandler( const Ast::PlacedIdentifier & id, const char * msg )
 446 {
 447   initDefineDynamic( id.clone( ),
 448                      Lang::THE_IDENTITY,
 449                      Helpers::newValHandle( new Lang::ExceptionWrapper< Exceptions::HandlerError >( id, msg ) ) );
 450 }
 451
 452 PtrOwner_back_Access< std::list< const Ast::PlacedIdentifier * > > Kernel::Environment::coreIdentifiers;
 453
 454 const Ast::PlacedIdentifier *
 455 Kernel::Environment::newPlacedIdentifier( const RefCountPtr< const Ast::NamespacePath > & path, const char * simpleId )
 456 {
 457   const Ast::PlacedIdentifier * id = new Ast::PlacedIdentifier( path, simpleId );
 458   coreIdentifiers.push_back( id );
 459   return id;
 460 }
 461
 462 const Ast::PlacedIdentifier *
 463 Kernel::Environment::newPlacedIdentifier( const Ast::PlacedIdentifier & id )
 464 {
 465   return newPlacedIdentifier( id.absolutePathRef( ), id.simpleId( ) );
 466 }
 467
 468 Kernel::Environment::Environment( std::list< Kernel::Environment * > & garbageArea, const char * debugName )
 469   : parent_( 0 ),
 470     bindings_( new Ast::IdentifierTree( NULL, false ) ),
 471     values_( new std::vector< Kernel::VariableHandle >( ) ),
 472     dynamicKeyBindings_( new Ast::IdentifierTree( NULL, false ) ),
 473     dynamicKeyValues_( new std::vector< DynamicVariableProperties * > ),
 474     stateBindings_( new Ast::IdentifierTree( NULL, false ) ),
 475     states_( new std::vector< Kernel::StateHandle >( ) ),
 476     dynamicStateKeyBindings_( new Ast::IdentifierTree( NULL, false ) ),
 477     dynamicStateKeyValues_( new std::vector< DynamicStateProperties * > ),
 478     debugName_( debugName )
 479 {
 480   garbageArea.push_back( this );
 481   ++createdCount;
 482   ++liveCount;
 483 }
 484
 485 Kernel::Environment::Environment( std::list< Kernel::Environment * > & garbageArea, Environment * parent, Ast::IdentifierTree * bindings, const RefCountPtr< std::vector< VariableHandle > > & values, Ast::IdentifierTree * stateBindings, const RefCountPtr< std::vector< StateHandle > > & states, const char * debugName )
 486   : parent_( parent ),
 487     bindings_( bindings ), values_( values ), dynamicKeyBindings_( NULL ),
 488     stateBindings_( stateBindings ), states_( states ), dynamicStateKeyBindings_( NULL ),
 489     debugName_( debugName )
 490                                  //, unitMap_( NullPtr< Kernel::Environment::UnitMapType >( ) )
 491 {
 492   garbageArea.push_back( this );
 493   //  if( parent_ != NULL )
 494   //    {
 495   //      unitMap_ = parent->unitMap_;
 496   //    }
 497   ++createdCount;
 498   ++liveCount;
 499 }
 500
 501 Kernel::Environment::~Environment( )
 502 {
 503   clear( );
 504   if( dynamicKeyBindings_ != NULL )
 505     {
 506       if( parent_ == NULL )
 507         {
 508           /* The condition means that this is the global evironment, which created its own map.
 509            */
 510           delete dynamicKeyBindings_;
 511         }
 512       /* However, the values will always be owned by the environment itself, and be defined whenever dynamicKeyBindings_ != NULL
 513        */
 514       for( std::vector< DynamicVariableProperties * >::iterator i = dynamicKeyValues_->begin( ); i != dynamicKeyValues_->end( ); ++i )
 515         {
 516           if( *i != NULL )
 517             {
 518               delete *i;
 519             }
 520         }
 521       delete dynamicKeyValues_;
 522     }
 523   if( stateBindings_ != NULL )
 524     {
 525       if( parent_ == NULL )
 526         {
 527           /* The condition means that this is the global evironment, which created its own map.
 528            */
 529           delete stateBindings_;
 530         }
 531       /* However, the values will always be owned by the environment itself, and be defined whenever dynamicKeyBindings_ != NULL
 532        */
 533       for( std::vector< StateHandle >::iterator i = states_->begin( ); i != states_->end( ); ++i )
 534         {
 535           if( *i != NULL )
 536             {
 537               delete *i;
 538             }
 539         }
 540     }
 541   if( dynamicStateKeyBindings_ != NULL )
 542     {
 543       if( parent_ == NULL )
 544         {
 545           /* The condition means that this is the global evironment, which created its own map.
 546            */
 547           delete dynamicStateKeyBindings_;
 548         }
 549       /* However, the values will always be owned by the environment itself, and be defined whenever dynamicKeyBindings_ != NULL
 550        */
 551       for( std::vector< DynamicStateProperties * >::iterator i = dynamicStateKeyValues_->begin( ); i != dynamicStateKeyValues_->end( ); ++i )
 552         {
 553           if( *i != NULL )
 554             {
 555               delete *i;
 556             }
 557         }
 558       delete dynamicStateKeyValues_;
 559     }
 560   --liveCount;
 561 }
 562
 563 void
 564 Kernel::Environment::setParent( Kernel::Environment * parent )
 565 {
 566   parent_ = parent;
 567   //  unitMap_ = parent.unitMap_;
 568 }
 569
 570 Kernel::Environment *
 571 Kernel::Environment::getParent( )
 572 {
 573   if( isBaseEnvironment( ) )
 574     {
 575       throw Exceptions::MiscellaneousRequirement( "Trying to find the parent of the top level environment." );
 576     }
 577   return parent_;
 578 }
 579
 580 const Kernel::Environment *
 581 Kernel::Environment::getParent( ) const
 582 {
 583   if( isBaseEnvironment( ) )
 584     {
 585       throw Exceptions::MiscellaneousRequirement( "Trying to find the parent of the top level environment." );
 586     }
 587   return parent_;
 588 }
 589
 590 void
 591 Kernel::Environment::setupDynamicKeyVariables( Ast::IdentifierTree * dynamicKeyBindings )
 592 {
 593   if( dynamicKeyBindings_ == NULL )
 594     {
 595       dynamicKeyBindings_ = dynamicKeyBindings;
 596       dynamicKeyValues_ = new std::vector< DynamicVariableProperties * >;
 597     }
 598   CHECK(
 599   else
 600     {
 601       if( dynamicKeyBindings_ != dynamicKeyBindings )
 602         {
 603           throw Exceptions::InternalError( "Kernel::Environment::setupDynamicKeyVariables: dynamicKeyBindings_ != dynamicKeyBindings" );
 604         }
 605     }
 606         );
 607   size_t theSize = dynamicKeyBindings_->size( );
 608   dynamicKeyValues_->reserve( theSize );
 609   while( dynamicKeyValues_->size( ) < theSize )
 610     {
 611       dynamicKeyValues_->push_back( 0 );
 612     }
 613 }
 614
 615 void
 616 Kernel::Environment::setupDynamicStateKeyVariables( Ast::IdentifierTree * dynamicStateKeyBindings )
 617 {
 618   if( dynamicStateKeyBindings_ == NULL )
 619     {
 620       dynamicStateKeyBindings_ = dynamicStateKeyBindings;
 621       dynamicStateKeyValues_ = new std::vector< DynamicStateProperties * >;
 622     }
 623   CHECK(
 624   else
 625     {
 626       if( dynamicStateKeyBindings_ != dynamicStateKeyBindings )
 627         {
 628           throw Exceptions::InternalError( "Kernel::Environment::setupDynamicStateKeyVariables: dynamicStateKeyBindings_ != dynamicStateKeyBindings" );
 629         }
 630     }
 631         );
 632   size_t theSize = dynamicStateKeyBindings_->size( );
 633   dynamicStateKeyValues_->reserve( theSize );
 634   while( dynamicStateKeyValues_->size( ) < theSize )
 635     {
 636       dynamicStateKeyValues_->push_back( 0 );
 637     }
 638 }
 639
 640 void
 641 Kernel::Environment::extendVectors( )
 642 {
 643   values_->reserve( bindings_->size( ) );
 644   while( values_->size( ) < bindings_->size( ) )
 645     {
 646       values_->push_back( NullPtr< Kernel::Variable >( ) );
 647     }
 648
 649   states_->reserve( stateBindings_->size( ) );
 650   while( states_->size( ) < stateBindings_->size( ) )
 651     {
 652       states_->push_back( NullPtr< Kernel::State >( ) );
 653     }
 654
 655 }
 656
 657 void
 658 Kernel::Environment::clear( )
 659 {
 660   /* Strange that this is empty...
 661    * The idea, though, is that the reference counting of this->values shall take care of deletion.
 662    */
 663 }
 664
 665 Ast::AnalysisEnvironment *
 666 Kernel::Environment::newAnalysisEnvironment( Ast::AnalysisEnvironment * parent ) const
 667 {
 668   Ast::AnalysisEnvironment * res = new Ast::AnalysisEnvironment( Ast::theAnalysisEnvironmentList, parent, bindings_, stateBindings_ );
 669   if( dynamicKeyBindings_ != NULL )
 670     {
 671       res->setupDynamicKeyVariables( dynamicKeyBindings_ );
 672     }
 673   if( dynamicStateKeyBindings_ != NULL )
 674     {
 675       res->setupDynamicStateKeyVariables( dynamicStateKeyBindings_ );
 676     }
 677
 678   return res;
 679 }
 680
 681 void
 682 Kernel::Environment::gcMark( Kernel::GCMarkedSet & marked )
 683 {
 684   if( gcMarked_ )
 685     {
 686       return;
 687     }
 688   gcMarked_ = true;
 689   marked.insert( marked.begin( ), this );
 690
 691   values_->clear( );
 692 }
 693
 694 void
 695 Kernel::Environment::collect( std::list< Kernel::Environment * > & garbageArea )
 696 {
 697   for( std::list< Kernel::Environment * >::iterator i = garbageArea.begin( ); i != garbageArea.end( ); ++i )
 698     {
 699       (*i)->clear_gcMarked( );
 700     }
 701
 702   Kernel::GCMarkedSet marked;
 703   for( std::list< Kernel::Environment * >::iterator i = garbageArea.begin( ); i != garbageArea.end( ); ++i )
 704     {
 705       (*i)->gcMark( marked );
 706     }
 707
 708   for( std::list< Kernel::Environment * >::iterator i = garbageArea.begin( ); i != garbageArea.end( ); )
 709     {
 710       if( (*i)->gcMarked( ) )
 711         {
 712           ++i;
 713           continue;
 714         }
 715       std::list< Kernel::Environment * >::iterator tmp = i;
 716       ++i;
 717       delete *tmp;
 718       garbageArea.erase( tmp );
 719     }
 720 }
 721
 722
 723 const size_t Ast::IdentifierTree::NOT_FOUND = std::numeric_limits< size_t >::max( );
 724
 725 Ast::IdentifierTree::IdentifierTree( IdentifierTree * parent, bool encapsulation )
 726   : size_( 0 ), root_( ( parent == NULL ) ? this : ( parent->root( ) ) ), encap_( ( encapsulation || parent == NULL ) ? this : ( parent->encap( ) ) ), encapParent_( encapsulation ? parent : NULL )
 727 { }
 728
 729 Ast::IdentifierTree::~IdentifierTree( )
 730 {
 731   typedef typeof namespaces_ MapType;
 732   for( MapType::iterator i = namespaces_.begin( ); i != namespaces_.end( ); ++i )
 733   {
 734     if( i->second.kind( ) != NamespaceLink::PRIMARY )
 735       continue;
 736     delete i->second.node( );
 737   }
 738 }
 739
 740 Ast::IdentifierTree *
 741 Ast::IdentifierTree::base( Ast::NamespaceReference::Base b )
 742 {
 743   switch( b ){
 744   case Ast::NamespaceReference::ABSOLUTE:
 745     return root_;
 746   case Ast::NamespaceReference::LOCAL:
 747     return encap_;
 748   case Ast::NamespaceReference::RELATIVE:
 749     return this;
 750   }
 751 }
 752
 753 const Ast::IdentifierTree *
 754 Ast::IdentifierTree::base( Ast::NamespaceReference::Base b ) const
 755 {
 756   switch( b ){
 757   case Ast::NamespaceReference::ABSOLUTE:
 758     return root_;
 759   case Ast::NamespaceReference::LOCAL:
 760     return encap_;
 761   case Ast::NamespaceReference::RELATIVE:
 762     return this;
 763   }
 764 }
 765
 766 Ast::IdentifierTree *
 767 Ast::IdentifierTree::newChild( const char * key, const Ast::SourceLocation & loc )
 768 {
 769   IdentifierTree * tree = new Ast::IdentifierTree( this, Ast::SearchContext::isEncapsulationName( key ) );
 770   typedef typeof namespaces_ MapType;
 771   namespaces_.insert( MapType::value_type( key, NamespaceLink( NamespaceLink::PRIMARY, tree ) ) );
 772   if( encapParent_ != NULL ){
 773     encapParent_->insertEncapsulationLink( key, tree, loc );
 774   }
 775   return tree;
 776 }
 777
 778 bool
 779 Ast::IdentifierTree::insert( const Ast::PlacedIdentifier & id, const Ast::SourceLocation & loc )
 780 {
 781   return insert( id.absolutePath( ).begin( ), id.absolutePath( ).end( ), id.simpleId( ), size_, loc );
 782 }
 783
 784 bool
 785 Ast::IdentifierTree::insertAlias( const Ast::PlacedIdentifier & id, const Ast::NamespaceReference & expansion, const Ast::SourceLocation & loc )
 786 {
 787   return insertAlias( id.absolutePath( ).begin( ), id.absolutePath( ).end( ), id.simpleId( ), expansion, loc );
 788 }
 789
 790 bool
 791 Ast::IdentifierTree::insert( Ast::NamespacePath::const_iterator begin, const Ast::NamespacePath::const_iterator & end, const char * simpleId, size_t pos, const Ast::SourceLocation & loc )
 792 {
 793   if( begin == end ){
 794
 795     typedef typeof simpleIdentifiers_ MapType;
 796     if( simpleIdentifiers_.find( simpleId ) != simpleIdentifiers_.end( ) )
 797       return false;
 798     simpleIdentifiers_.insert( MapType::value_type( simpleId, pos ) );
 799     ++size_;
 800     if( encapParent_ != NULL ){
 801       encapParent_->insertEncapsulationLink( simpleId, pos, loc );
 802     }
 803     return true;
 804
 805   }else{
 806
 807     typedef typeof namespaces_ MapType;
 808     MapType::iterator j = namespaces_.find( *begin );
 809     if( j != namespaces_.end( ) ){
 810
 811       bool result = j->second.node( )->insert( ++begin, end, simpleId, pos, loc );
 812       if (result)
 813         ++size_;
 814       return result;
 815
 816     }else{
 817
 818       IdentifierTree * tree = newChild( *begin, loc );
 819       bool result = tree->insert( ++begin, end, simpleId, pos, loc );
 820       if (result)
 821         ++size_;
 822       return result;
 823
 824     }
 825
 826   }
 827 }
 828
 829 bool
 830 Ast::IdentifierTree::insertAlias( Ast::NamespacePath::const_iterator begin, const Ast::NamespacePath::const_iterator & end, const char * simpleId, const Ast::NamespaceReference & expansion, const Ast::SourceLocation & loc )
 831 {
 832   if( begin == end ){
 833
 834     bool found;
 835     IdentifierTree * tree = resolveAlias( expansion, & found, loc );
 836
 837     typedef typeof namespaces_ MapType;
 838     MapType::iterator j = namespaces_.find( simpleId );
 839     if( j != namespaces_.end( ) ){
 840       Ast::theAnalysisErrorsList.push_back( new Exceptions::NamespaceAliasCollision( loc, this, simpleId ) );
 841     }else{
 842       namespaces_.insert( MapType::value_type( simpleId, NamespaceLink( NamespaceLink::RESTRICTED, tree ) ) );
 843     }
 844
 845     return found;
 846
 847   }else{
 848
 849     typedef typeof namespaces_ MapType;
 850     MapType::iterator j = namespaces_.find( *begin );
 851     if( j != namespaces_.end( ) ){
 852
 853       return j->second.node( )->insertAlias( ++begin, end, simpleId, expansion, loc );
 854
 855     }else{
 856
 857       IdentifierTree * tree = newChild( *begin, loc );
 858       return tree->insertAlias( ++begin, end, simpleId, expansion, loc );
 859
 860     }
 861
 862   }
 863 }
 864
 865 Ast::IdentifierTree *
 866 Ast::IdentifierTree::resolveAlias( const Ast::NamespaceReference & expansion, bool * found, const Ast::SourceLocation & loc )
 867 {
 868   *found = true;
 869   return base( expansion.base( ) )->resolveAlias( expansion.path( ).begin( ), expansion.path( ).end( ), found, loc );
 870 }
 871
 872 Ast::IdentifierTree *
 873 Ast::IdentifierTree::resolveAlias( const Ast::NamespacePath::const_iterator & begin, const Ast::NamespacePath::const_iterator & end, bool * found, const Ast::SourceLocation & loc )
 874 {
 875   if( begin == end ){
 876
 877     return this;
 878
 879   }else{
 880
 881     Ast::NamespacePath::const_iterator next(begin);
 882     ++next;
 883     typedef typeof namespaces_ MapType;
 884     MapType::const_iterator j = namespaces_.find( *begin );
 885     if( j == namespaces_.end( ) ){
 886       *found = false;
 887       IdentifierTree * tree = newChild( *begin, loc );
 888       return tree->resolveAlias( next, end, found, loc );
 889     }
 890
 891     return j->second.node( )->resolveAlias( next, end, found, loc );
 892
 893   }
 894 }
 895
 896 void
 897 Ast::IdentifierTree::insertEncapsulationLink( const char * key, size_t pos, const Ast::SourceLocation & loc )
 898 {
 899   typedef typeof simpleIdentifiers_ MapType;
 900   if( simpleIdentifiers_.find( key ) != simpleIdentifiers_.end( ) ){
 901     Ast::theAnalysisErrorsList.push_back( new Exceptions::EncapsulationIntroducingExisting( loc, key ) );
 902     return;
 903   }
 904   simpleIdentifiers_.insert( MapType::value_type( key, pos ) );
 905 }
 906
 907 void
 908 Ast::IdentifierTree::insertEncapsulationLink( const char * key, Ast::IdentifierTree * tree, const Ast::SourceLocation & loc )
 909 {
 910   typedef typeof namespaces_ MapType;
 911   if( namespaces_.find( key ) != namespaces_.end( ) ){
 912     Ast::theAnalysisErrorsList.push_back( new Exceptions::EncapsulationNamespaceAliasCollision( loc, key ) );
 913     return;
 914   }
 915   namespaces_.insert( MapType::value_type( key, NamespaceLink( NamespaceLink::SECONDARY, tree ) ) );
 916 }
 917
 918 size_t
 919 Ast::IdentifierTree::lookup( const Ast::Identifier & id ) const
 920 {
 921   const Ast::SearchContext & context = id.searchContext( );
 922
 923   switch( id.base( ) ){
 924   case Ast::NamespaceReference::ABSOLUTE:
 925     return lookupSuffix( false, id.path( ).begin( ), id.path( ).end( ), id.simpleId( ) );
 926
 927   case Ast::NamespaceReference::LOCAL:
 928     return lookupInside( context.encapsulationPath( )->begin( ), context.encapsulationPath( )->end( ), id );
 929
 930   case Ast::NamespaceReference::RELATIVE:
 931     {
 932       size_t pos = lookupPrefix( context.lexicalPath( )->begin( ), context.lexicalPath( )->end( ), context.privateName( ).getPtr( ), id );
 933       if( pos != NOT_FOUND )
 934         return pos;
 935     }
 936     for( RefCountPtr< const Ast::LookinPathStack > i( context.lookinStack( ) ); i != NullPtr< const Ast::LookinPathStack >( ); i = i->cdr( ) ){
 937       size_t pos = lookupInside( i->car( )->begin( ), i->car( )->end( ), id );
 938       if( pos != NOT_FOUND )
 939         return pos;
 940     }
 941     break;
 942   }
 943
 944   return NOT_FOUND;
 945 }
 946
 947 size_t
 948 Ast::IdentifierTree::lookup( const Ast::PlacedIdentifier & id ) const
 949 {
 950   return lookupSuffix( false, id.absolutePath( ).begin( ), id.absolutePath( ).end( ), id.simpleId( ) );
 951 }
 952
 953 size_t
 954 Ast::IdentifierTree::lookupPrivateAlias( const Ast::PlacedIdentifier & id, const char * privateName ) const
 955 {
 956   /* Mimic how a relative identifier would be looked up with lookupPrefix, but only consider the private namespace.
 957    */
 958   if( privateName == NULL )
 959     return NOT_FOUND;
 960
 961   const Ast::IdentifierTree * tree = this;
 962   Ast::NamespacePath::const_iterator i = id.absolutePath( ).begin( );
 963   Ast::NamespacePath::const_iterator end = id.absolutePath( ).end( );
 964   for( ; i != end; ++i ){
 965     typedef typeof namespaces_ MapType;
 966     MapType::const_iterator j = tree->namespaces_.find( *i );
 967     if( j == tree->namespaces_.end( ) )
 968       break;
 969     tree = j->second.node( );
 970   }
 971   if( i != end )
 972     return NOT_FOUND;
 973
 974   typedef typeof namespaces_ MapType;
 975   MapType::const_iterator j = tree->namespaces_.find( privateName );
 976   if( j == tree->namespaces_.end( ) )
 977     return NOT_FOUND;
 978
 979   /* We must pass an empty NamespacePath range, and id.absolutePath( ).begin( ) .. id.absolutePath( ).begin( )
 980    * happens to be available.
 981    */
 982   return j->second.node( )->lookupSuffix( false, id.absolutePath( ).begin( ), id.absolutePath( ).begin( ), id.simpleId( ) );
 983 }
 984
 985 size_t
 986 Ast::IdentifierTree::lookupPrefix( const Ast::NamespacePath::const_iterator & begin, const Ast::NamespacePath::const_iterator & end, const char * privateName, const Ast::Identifier & id ) const
 987 {
 988   std::stack< const Ast::IdentifierTree * > path;
 989
 990   const Ast::IdentifierTree * tree = this;
 991   path.push( tree );
 992   Ast::NamespacePath::const_iterator i = begin;
 993   for( ; i != end; ++i ){
 994     typedef typeof namespaces_ MapType;
 995     MapType::const_iterator j = tree->namespaces_.find( *i );
 996     if( j == tree->namespaces_.end( ) )
 997       break;
 998     tree = j->second.node( );
 999     path.push( tree );
1000   }
1001
1002   /* Look in local namespace.
1003    * Only do this for identifiers with empty relative path, and inside
1004    * the current namespace.
1005    */
1006   if( i == end && id.path( ).empty( ) && privateName != NULL ){
1007     typedef typeof namespaces_ MapType;
1008     MapType::const_iterator j = tree->namespaces_.find( privateName );
1009     if( j != tree->namespaces_.end( ) ){
1010
1011       size_t pos = j->second.node( )->lookupSuffix( false, id.path( ).begin( ), id.path( ).end( ), id.simpleId( ) );
1012       if( pos != NOT_FOUND )
1013         return pos;
1014
1015     }
1016   }
1017
1018   while( ! path.empty( ) ){
1019     tree = path.top( );
1020     path.pop( );
1021       size_t pos = tree->lookupSuffix( true, id.path( ).begin( ), id.path( ).end( ), id.simpleId( ) );
1022       if( pos != NOT_FOUND )
1023         return pos;
1024     if( tree->encapParent_ != NULL )
1025       break;
1026   }
1027   return NOT_FOUND;
1028 }
1029
1030 size_t Ast::IdentifierTree::lookupInside( const Ast::NamespacePath::const_iterator & begin, const Ast::NamespacePath::const_iterator & end, const Ast::Identifier & id ) const
1031 {
1032   if( begin == end ){
1033     return lookupSuffix( false, id.path( ).begin( ), id.path( ).end( ), id.simpleId( ) );
1034   }
1035
1036   typedef typeof namespaces_ MapType;
1037   MapType::const_iterator i = namespaces_.find( *begin );
1038   if( i == namespaces_.end( ) )
1039     return NOT_FOUND;
1040   if( i->second.kind( ) != NamespaceLink::PRIMARY )
1041     return NOT_FOUND;
1042
1043   Ast::NamespacePath::const_iterator next = begin;
1044   ++next;
1045   return i->second.node( )->lookupInside( next, end, id );
1046 }
1047
1048 size_t
1049 Ast::IdentifierTree::lookupSuffix( bool followRestricted, const Ast::NamespacePath::const_iterator & begin, const Ast::NamespacePath::const_iterator & end, const char * simpleId ) const
1050 {
1051   if( begin == end ){
1052
1053     typedef typeof simpleIdentifiers_ MapType;
1054     MapType::const_iterator i = simpleIdentifiers_.find( simpleId );
1055     if( i == simpleIdentifiers_.end( ) )
1056       return NOT_FOUND;
1057
1058     return i->second;
1059
1060   }else{
1061
1062     const char * front = *begin;
1063     typedef typeof namespaces_ MapType;
1064     MapType::const_iterator i = namespaces_.find( front );
1065     if( i == namespaces_.end( ) )
1066       return NOT_FOUND;
1067     if( ! followRestricted && i->second.kind( ) == NamespaceLink::RESTRICTED )
1068       return NOT_FOUND;
1069
1070     Ast::NamespacePath::const_iterator next(begin);
1071     ++next;
1072     return i->second.node( )->lookupSuffix( false, next, end, simpleId );
1073
1074   }
1075 }
1076
1077
1078 Ast::PlacedIdentifier
1079 Ast::IdentifierTree::reverseMap( size_t pos ) const
1080 {
1081   const char * simpleId;
1082   std::list< const char * > * absolutePath = reverseMapHelper( pos, & simpleId );
1083   if( absolutePath == NULL )
1084     throw Exceptions::InternalError( "Ast::IdentifierTree::reverseMap failure." );
1085   return Ast::PlacedIdentifier( absolutePath, simpleId );
1086 }
1087
1088 std::list< const char * > *
1089 Ast::IdentifierTree::reverseMapHelper( size_t pos, const char ** simpleIdDst ) const
1090 {
1091   {
1092     typedef typeof simpleIdentifiers_ MapType;
1093     for( MapType::const_iterator i = simpleIdentifiers_.begin( ); i != simpleIdentifiers_.end( ); ++i ){
1094       if( i->second == pos )
1095         {
1096           std::list< const char * > * result( new std::list< const char * > );
1097           *simpleIdDst = i->first;
1098           return result;
1099         }
1100     }
1101   }
1102
1103   {
1104     typedef typeof namespaces_ MapType;
1105     for( MapType::const_iterator i = namespaces_.begin( ); i != namespaces_.end( ); ++i ){
1106       if( i->second.kind( ) != NamespaceLink::PRIMARY )
1107         continue;
1108       std::list< const char * > * path = i->second.node( )->reverseMapHelper( pos, simpleIdDst );
1109       if( path == NULL )
1110         continue;
1111       path->push_front( i->first );
1112       return path;
1113     }
1114   }
1115
1116   return NULL;
1117 }
1118
1119 void
1120 Ast::IdentifierTree::dumpMap( std::map< Ast::PlacedIdentifier, size_t > * dst ) const
1121 {
1122   Ast::NamespacePath path;
1123   dumpMap( dst, & path );
1124 }
1125
1126 void
1127 Ast::IdentifierTree::dumpMap( std::map< Ast::PlacedIdentifier, size_t > * dst, Ast::NamespacePath * path ) const
1128 {
1129   {
1130     typedef typeof simpleIdentifiers_ MapType;
1131     typedef typeof *dst DstType;
1132     for( MapType::const_iterator i = simpleIdentifiers_.begin( ); i != simpleIdentifiers_.end( ); ++i ){
1133       dst->insert( DstType::value_type( Ast::PlacedIdentifier( *path, i->first ), i->second ) );
1134     }
1135   }
1136
1137   {
1138     typedef typeof namespaces_ MapType;
1139     for( MapType::const_iterator i = namespaces_.begin( ); i != namespaces_.end( ); ++i ){
1140       path->push_back( i->first );
1141       i->second.node( )->dumpMap( dst, path );
1142       path->pop_back( );
1143     }
1144   }
1145 }
1146
1147 void
1148 Ast::IdentifierTree::showPath( std::ostream & os ) const
1149 {
1150   typedef std::list< const char * > ListType;
1151   ListType path;
1152   if( ! root_->pushPath( this, & path ) ) {
1153     throw Exceptions::InternalError( "IdentifierTree::showPath failed to find namespace path." );
1154   }
1155   for (ListType::const_iterator i = path.begin( ); i != path.end( ); ++i ){
1156     os << Interaction::NAMESPACE_SEPARATOR << *i ;
1157   }
1158 }
1159
1160 bool
1161 Ast::IdentifierTree::pushPath( const Ast::IdentifierTree * tree, std::list< const char * > * dst ) const
1162 {
1163   /* Special case for empty path. */
1164   if( tree == this )
1165     return true;
1166
1167   typedef typeof namespaces_ MapType;
1168   for( MapType::const_iterator i = namespaces_.begin( ); i != namespaces_.end( ); ++i ){
1169     if( i->second.kind( ) != NamespaceLink::PRIMARY )
1170       continue;
1171     const Ast::IdentifierTree * node( i->second.node( ) );
1172     if( node == tree ){
1173       if( node->encapParent_ == NULL )
1174         dst->push_front( i->first );
1175       return true;
1176     }
1177     if( ! node->pushPath( tree, dst ) )
1178       continue;
1179     if( node->encapParent_ == NULL )
1180       dst->push_front( i->first );
1181     return true;
1182   }
1183
1184   return false;
1185 }
1186
1187
1188 Ast::StateID Ast::AnalysisEnvironment::nextStateID = 1;
1189
1190 Ast::AnalysisEnvironment::AnalysisEnvironment( PtrOwner_back_Access< std::list< Ast::AnalysisEnvironment * > > & deleter, Ast::AnalysisEnvironment * parent, const Ast::IdentifierTree * bindings, const Ast::IdentifierTree * stateBindings )
1191   : parent_( parent ),
1192     level_( ( parent_ == NULL ) ? 0 : ( parent_->level_ + 1 ) ),
1193     bindings_( bindings ), dynamicKeyBindings_( NULL ),
1194     stateBindings_( stateBindings ), dynamicStateKeyBindings_( NULL ),
1195     functionBoundary_( false )
1196 {
1197   deleter.push_back( this );
1198   updateBindings( );
1199 }
1200
1201 Ast::AnalysisEnvironment::~AnalysisEnvironment( )
1202 { }
1203
1204 void
1205 Ast::AnalysisEnvironment::updateBindings( )
1206 {
1207   states_.reserve( stateBindings_->size( ) );
1208   while( states_.size( ) < stateBindings_->size( ) )
1209     {
1210       states_.push_back( nextStateID );
1211       ++nextStateID;
1212     }
1213
1214   statesFirstUse_.resize( stateBindings_->size( ), NULL );
1215 }
1216
1217 Ast::AnalysisEnvironment *
1218 Ast::AnalysisEnvironment::getParent( ) const
1219 {
1220   if( isBaseEnvironment( ) )
1221     {
1222       throw Exceptions::MiscellaneousRequirement( "Trying to find the parent of the top level analysis environment." );
1223     }
1224   return parent_;
1225 }
1226
1227 void
1228 Ast::AnalysisEnvironment::activateFunctionBoundary( )
1229 {
1230   functionBoundary_ = true;
1231 }
1232
1233 void
1234 Ast::AnalysisEnvironment::setupDynamicKeyVariables( const Ast::IdentifierTree * dynamicKeyBindings )
1235 {
1236   dynamicKeyBindings_ = dynamicKeyBindings;
1237 }
1238
1239 void
1240 Ast::AnalysisEnvironment::setupDynamicStateKeyVariables( const Ast::IdentifierTree * dynamicStateKeyBindings )
1241 {
1242   dynamicStateKeyBindings_ = dynamicStateKeyBindings;
1243 }
1244
1245 size_t
1246 Ast::AnalysisEnvironment::findLocalVariablePosition( const Ast::SourceLocation & loc, const Ast::PlacedIdentifier & id ) const
1247 {
1248   size_t pos = bindings_->lookup( id );
1249   if( pos == Ast::IdentifierTree::NOT_FOUND )
1250     {
1251       throw Exceptions::InternalError( loc, "Environment::findLocalPosition failed" );
1252     }
1253   return pos;
1254 }
1255
1256 void
1257 Kernel::Environment::define( size_t pos, const Kernel::VariableHandle & val )
1258 {
1259   if( (*values_)[ pos ] != NullPtr< Kernel::Variable >( ) )
1260     {
1261       throw Exceptions::RedefiningLexical( bindings_->reverseMap( pos ) );
1262     }
1263
1264   (*values_)[ pos ] = val;
1265 }
1266
1267 Kernel::Environment::LexicalKey
1268 Ast::AnalysisEnvironment::findLexicalVariableKey( const Ast::SourceLocation & loc, const Ast::Identifier & id ) const
1269 {
1270   size_t pos = bindings_->lookup( id );
1271   if( pos == Ast::IdentifierTree::NOT_FOUND )
1272     {
1273       if( isBaseEnvironment( ) )
1274         {
1275           Ast::theAnalysisErrorsList.push_back( new Exceptions::LookupUnknown( loc, id, Ast::Identifier::VARIABLE ) );
1276           return Kernel::Environment::theMissingKey;
1277         }
1278       return parent_->findLexicalVariableKey( loc, id ).oneAbove( );
1279     }
1280
1281   return LexicalKey( 0, pos );
1282 }
1283
1284 Kernel::Environment::LexicalKey
1285 Ast::AnalysisEnvironment::findPrivateAliasVariableKey( const Ast::SourceLocation & loc, const Ast::PlacedIdentifier & id, const char * privateName ) const
1286 {
1287   size_t pos = bindings_->lookupPrivateAlias( id, privateName );
1288   if( pos == Ast::IdentifierTree::NOT_FOUND ){
1289     Ast::theAnalysisErrorsList.push_back( new Exceptions::LookupUnknownPrivateAlias( loc, id, Ast::Identifier::VARIABLE ) );
1290     return Kernel::Environment::theMissingKey;
1291   }
1292
1293   return LexicalKey( 0, pos );
1294 }
1295
1296 Ast::PlacedIdentifier
1297 Ast::AnalysisEnvironment::reverseMapLexicalVariable( const LexicalKey & lexKey ) const
1298 {
1299   const AnalysisEnvironment * env = this;
1300   for( size_t i = lexKey.up_; i > 0; --i )
1301     {
1302       env = env->getParent( );
1303     }
1304
1305     return env->bindings_->reverseMap( lexKey.pos_ );
1306 }
1307
1308 void
1309 Kernel::Environment::lookup( const Kernel::Environment::LexicalKey & lexKey, Kernel::EvalState * evalState ) const
1310 {
1311   const Environment * env = this;
1312   for( size_t i = lexKey.up_; i > 0; --i )
1313     {
1314       env = env->getParent( );
1315     }
1316
1317   env->lookup( lexKey.pos_, evalState );
1318 }
1319
1320 void
1321 Kernel::Environment::lookup( size_t pos, Kernel::EvalState * evalState ) const
1322 {
1323   Kernel::VariableHandle res = (*values_)[ pos ];
1324   if( res == NullPtr< Kernel::Variable >( ) )
1325     {
1326       throw Exceptions::UninitializedAccess( );
1327     }
1328
1329   Kernel::ContRef cont = evalState->cont_;
1330   cont->takeHandle( res, evalState );
1331 }
1332
1333 Kernel::VariableHandle
1334 Kernel::Environment::getVarHandle( const Kernel::Environment::LexicalKey & lexKey )
1335 {
1336   Environment * env = this;
1337   for( size_t i = lexKey.up_; i > 0; --i )
1338     {
1339       env = env->getParent( );
1340     }
1341
1342   return env->getVarHandle( lexKey.pos_ );
1343 }
1344
1345 Kernel::VariableHandle
1346 Kernel::Environment::getVarHandle( size_t pos )
1347 {
1348   return (*values_)[ pos ];
1349 }
1350
1351 Kernel::Environment::LexicalKey
1352 Ast::AnalysisEnvironment::findLexicalTypeKey( const Ast::SourceLocation & loc, const Ast::Identifier & id ) const
1353 {
1354   size_t pos = bindings_->lookup( id );
1355   if( pos == Ast::IdentifierTree::NOT_FOUND )
1356     {
1357       if( isBaseEnvironment( ) )
1358         {
1359           Ast::theAnalysisErrorsList.push_back( new Exceptions::LookupUnknown( loc, id, Ast::Identifier::TYPE ) );
1360           return Kernel::Environment::theMissingKey;
1361         }
1362       return parent_->findLexicalTypeKey( loc, id ).oneAbove( );
1363     }
1364
1365   return LexicalKey( 0, pos );
1366 }
1367
1368
1369 size_t
1370 Ast::AnalysisEnvironment::findLocalStatePosition( const Ast::SourceLocation & loc, const Ast::PlacedIdentifier & id ) const
1371 {
1372   size_t pos = stateBindings_->lookup( id );
1373   if( pos == Ast::IdentifierTree::NOT_FOUND )
1374     {
1375       throw Exceptions::InternalError( loc, "Environment::findLocalStatePosition failed" );
1376     }
1377   return pos;
1378 }
1379
1380 Kernel::Environment::LexicalKey
1381 Ast::AnalysisEnvironment::findLexicalStateKey( const Ast::SourceLocation & loc, const Ast::Identifier & id, const Ast::Node * node )
1382 {
1383   size_t pos = stateBindings_->lookup( id );
1384   if( pos == Ast::IdentifierTree::NOT_FOUND )
1385     {
1386       if( isBaseEnvironment( ) )
1387         {
1388           Ast::theAnalysisErrorsList.push_back( new Exceptions::LookupUnknown( loc, id, Ast::Identifier::STATE ) );
1389           return Kernel::Environment::theMissingKey;
1390         }
1391       if( functionBoundary_ )
1392         {
1393           // If the state is not found at all, this will throw an error.
1394           parent_->findLexicalStateKey( loc, id, node ).oneAbove( );  // Ignore the result!
1395           // If no error is thrown, we inform the user that the state is outside a function boundary.
1396           Ast::theAnalysisErrorsList.push_back( new Exceptions::StateBeyondFunctionBoundary( loc, id ) );
1397           return Kernel::Environment::theMissingKey;
1398         }
1399       return parent_->findLexicalStateKey( loc, id, node ).oneAbove( );
1400     }
1401
1402   if( statesFirstUse_[ pos ] == NULL ){
1403     statesFirstUse_[ pos ] = node;
1404   }
1405
1406   return LexicalKey( 0, pos );
1407 }
1408
1409 Ast::StateID
1410 Ast::AnalysisEnvironment::getStateID( const LexicalKey & lexKey ) const
1411 {
1412   const Ast::AnalysisEnvironment * env = this;
1413   for( size_t i = lexKey.up_; i > 0; --i )
1414     {
1415       env = env->getParent( );
1416     }
1417
1418   return env->getStateID( lexKey.pos_ );
1419 }
1420
1421 Ast::StateID
1422 Ast::AnalysisEnvironment::getStateID( size_t pos ) const
1423 {
1424   return states_[ pos ];
1425 }
1426
1427 Ast::StateID
1428 Ast::AnalysisEnvironment::getTheAnyStateID( )
1429 {
1430   return -1;
1431 }
1432
1433 const Ast::Node *
1434 Ast::AnalysisEnvironment::getStateFirstUse( size_t pos ) const
1435 {
1436   return statesFirstUse_[ pos ];
1437 }
1438
1439 void
1440 Kernel::Environment::introduceState( size_t pos, Kernel::State * state )
1441 {
1442   if( (*states_)[ pos ] != NullPtr< Kernel::State >( ) )
1443     {
1444       throw Exceptions::InternalError( "Better error message needed when a state is introduced more than once." );
1445       //      throw Exceptions::RedefiningLexical( reverseMap( pos ) );
1446     }
1447
1448   (*states_)[ pos ] = state;
1449 }
1450
1451 void
1452 Kernel::Environment::freeze( size_t pos, Kernel::EvalState * evalState, const Ast::SourceLocation & loc )
1453 {
1454   if( (*states_)[ pos ] == NullPtr< Kernel::State >( ) )
1455     {
1456       /* This is a static inconsistency, so it should be detected before we reach here... */
1457       throw Exceptions::FreezingUndefined( loc, stateBindings_->reverseMap( pos ) );
1458     }
1459
1460   Kernel::StateHandle & state = (*states_)[ pos ];
1461
1462   state->freeze( evalState, loc );
1463 }
1464
1465 void
1466 Kernel::Environment::peek( const LexicalKey & lexKey, Kernel::EvalState * evalState, const Ast::SourceLocation & loc )
1467 {
1468   getStateHandle( lexKey )->peek( evalState, loc );
1469 }
1470
1471 void
1472 Kernel::Environment::tackOn( const LexicalKey & lexKey, Kernel::EvalState * evalState, const RefCountPtr< const Lang::Value > & piece, const Ast::SourceLocation & callLoc )
1473 {
1474   getStateHandle( lexKey )->tackOn( evalState, piece, callLoc );
1475 }
1476
1477 Kernel::StateHandle
1478 Kernel::Environment::getStateHandle( const LexicalKey & lexKey )
1479 {
1480   Environment * env = this;
1481   for( size_t i = lexKey.up_; i > 0; --i )
1482     {
1483       env = env->getParent( );
1484     }
1485
1486   return env->getStateHandle( lexKey.pos_ );
1487 }
1488
1489 Kernel::StateHandle
1490 Kernel::Environment::getStateHandle( size_t pos )
1491 {
1492   Kernel::StateHandle res = (*states_)[ pos ];
1493   if( res == NullPtr< Kernel::State >( ) )
1494     {
1495       throw Exceptions::UninitializedAccess( );
1496     }
1497   return res;
1498 }
1499
1500
1501
1502 size_t
1503 Ast::AnalysisEnvironment::findLocalDynamicPosition( const Ast::SourceLocation & loc, const Ast::PlacedIdentifier & id ) const
1504 {
1505   if( dynamicKeyBindings_ == NULL )
1506     {
1507       throw Exceptions::InternalError( "Environment::findLocalDynamicPosition called with dynamicKeyBindings_ == NULL." );
1508     }
1509   size_t pos = dynamicKeyBindings_->lookup( id );
1510   if( pos == Ast::IdentifierTree::NOT_FOUND )
1511     {
1512       throw Exceptions::InternalError( loc, "Environment::findLocalDynamicPosition failed" );
1513     }
1514   return pos;
1515 }
1516
1517 void
1518 Kernel::Environment::defineDynamic( const Ast::PlacedIdentifier * debugId, size_t pos, const RefCountPtr< const Lang::Function > & filter, const Kernel::VariableHandle & defaultVal )
1519 {
1520   if( dynamicKeyValues_ == NULL )
1521     {
1522       throw Exceptions::InternalError( "Environment::defineDynamic called with dynamicKeyValues_ == NULL." );
1523     }
1524   if( pos > dynamicKeyValues_->size( ) )
1525     {
1526       throw Exceptions::InternalError( "Environment::defineDynamic called with pos out of range." );
1527     }
1528   if( (*dynamicKeyValues_)[ pos ] != NULL )
1529     {
1530       throw Exceptions::RedefiningDynamic( dynamicKeyBindings_->reverseMap( pos ) );
1531     }
1532
1533   (*dynamicKeyValues_)[ pos ] = new Kernel::UserDynamicVariableProperties( debugId,
1534                                                                            Kernel::DynamicEnvironment::getFreshKey( ),
1535                                                                            filter,
1536                                                                            defaultVal );
1537 }
1538
1539 Kernel::Environment::LexicalKey
1540 Ast::AnalysisEnvironment::findLexicalDynamicKey( const Ast::SourceLocation & loc, const Ast::Identifier & id ) const
1541 {
1542   if( dynamicKeyBindings_ == NULL )
1543     {
1544       if( isBaseEnvironment( ) )
1545         {
1546           goto error;
1547         }
1548       return parent_->findLexicalDynamicKey( loc, id ).oneAbove( );
1549     }
1550   {
1551     size_t pos = dynamicKeyBindings_->lookup( id );
1552     if( pos == Ast::IdentifierTree::NOT_FOUND )
1553       {
1554         if( isBaseEnvironment( ) )
1555           {
1556             goto error;
1557           }
1558         return parent_->findLexicalDynamicKey( loc, id ).oneAbove( );
1559       }
1560
1561     return LexicalKey( 0, pos );
1562   }
1563
1564  error:
1565   Ast::theAnalysisErrorsList.push_back( new Exceptions::LookupUnknown( loc, id, Ast::Identifier::DYNAMIC_VARIABLE ) );
1566   return Kernel::Environment::theMissingKey;
1567 }
1568
1569 const Kernel::DynamicVariableProperties &
1570 Kernel::Environment::lookupDynamicVariable( const LexicalKey & lexKey ) const
1571 {
1572   const Environment * env = this;
1573   for( size_t i = lexKey.up_; i > 0; --i )
1574     {
1575       env = env->getParent( );
1576     }
1577
1578   return env->lookupDynamicVariable( lexKey.pos_ );
1579 }
1580
1581 const Kernel::DynamicVariableProperties &
1582 Kernel::Environment::lookupDynamicVariable( size_t pos ) const
1583 {
1584   const DynamicVariableProperties * res = (*dynamicKeyValues_)[ pos ];
1585   if( res == NULL )
1586     {
1587       throw Exceptions::UninitializedAccess( );
1588     }
1589   return *res;
1590 }
1591
1592 size_t
1593 Ast::AnalysisEnvironment::findLocalDynamicStatePosition( const Ast::SourceLocation & loc, const Ast::PlacedIdentifier & id ) const
1594 {
1595   if( dynamicStateKeyBindings_ == NULL )
1596     {
1597       throw Exceptions::InternalError( "Environment::findLocalDynamicStatePosition called with dynamicStateKeyBindings_ == NULL." );
1598     }
1599   size_t pos = dynamicStateKeyBindings_->lookup( id );
1600   if( pos == Ast::IdentifierTree::NOT_FOUND )
1601     {
1602       throw Exceptions::InternalError( loc, "Environment::findLocalDynamicStatePosition failed" );
1603     }
1604   return pos;
1605 }
1606
1607 void
1608 Kernel::Environment::defineDynamicState( const Ast::PlacedIdentifier * debugId, size_t pos, Kernel::PassedEnv env, Kernel::PassedDyn dyn, Ast::StateReference * defaultState )
1609 {
1610   if( dynamicStateKeyValues_ == NULL )
1611     {
1612       throw Exceptions::InternalError( "Environment::defineDynamicState called with dynamicStateKeyValues_ == NULL." );
1613     }
1614   if( pos > dynamicStateKeyValues_->size( ) )
1615     {
1616       throw Exceptions::InternalError( "Environment::defineDynamicState called with pos out of range." );
1617     }
1618   if( (*dynamicStateKeyValues_)[ pos ] != NULL )
1619     {
1620       throw Exceptions::RedefiningDynamic( dynamicStateKeyBindings_->reverseMap( pos ) );
1621     }
1622
1623   (*dynamicStateKeyValues_)[ pos ] = new Kernel::UserDynamicStateProperties( debugId, env, dyn, defaultState );
1624 }
1625
1626
1627 Kernel::Environment::LexicalKey
1628 Ast::AnalysisEnvironment::findLexicalDynamicStateKey( const Ast::SourceLocation & loc, const Ast::Identifier & id ) const
1629 {
1630   if( dynamicStateKeyBindings_ == NULL )
1631     {
1632       return parent_->findLexicalDynamicStateKey( loc, id ).oneAbove( );
1633     }
1634
1635   size_t pos = dynamicStateKeyBindings_->lookup( id );
1636   if( pos == Ast::IdentifierTree::NOT_FOUND )
1637     {
1638       if( isBaseEnvironment( ) )
1639         {
1640           Ast::theAnalysisErrorsList.push_back( new Exceptions::LookupUnknown( loc, id, Ast::Identifier::DYNAMIC_STATE ) );
1641           return Kernel::Environment::theMissingKey;
1642         }
1643       return parent_->findLexicalDynamicStateKey( loc, id ).oneAbove( );
1644     }
1645
1646   return LexicalKey( 0, pos );
1647 }
1648
1649 const Kernel::DynamicStateProperties &
1650 Kernel::Environment::lookupDynamicState( const LexicalKey & lexKey ) const
1651 {
1652   const Environment * env = this;
1653   for( size_t i = lexKey.up_; i > 0; --i )
1654     {
1655       env = env->getParent( );
1656     }
1657
1658   return env->lookupDynamicState( lexKey.pos_ );
1659 }
1660
1661 const Kernel::DynamicStateProperties &
1662 Kernel::Environment::lookupDynamicState( size_t pos ) const
1663 {
1664   const DynamicStateProperties * res = (*dynamicStateKeyValues_)[ pos ];
1665   if( res == NULL )
1666     {
1667       throw Exceptions::UninitializedAccess( );
1668     }
1669   return *res;
1670 }
1671
1672
1673 size_t
1674 Kernel::Environment::size( ) const
1675 {
1676   return bindings_->size( );
1677 }
1678
1679
1680 void
1681 Kernel::Environment::print( std::ostream & os ) const
1682 {
1683   std::set< Ast::PlacedIdentifier > shadowed;
1684   std::set< Ast::PlacedIdentifier > shadowedStates;
1685   recursivePrint( os, & shadowed, & shadowedStates );
1686 }
1687
1688 size_t
1689 Kernel::Environment::recursivePrint( std::ostream & os, std::set< Ast::PlacedIdentifier > * shadowed, std::set< Ast::PlacedIdentifier > * shadowedStates ) const
1690 {
1691   typedef std::map< Ast::PlacedIdentifier, size_t > IdMap;
1692
1693   std::set< Ast::PlacedIdentifier > shadowedBefore( *shadowed );
1694   std::set< Ast::PlacedIdentifier > shadowedStatesBefore( *shadowedStates );
1695
1696   size_t depth = 0;
1697   if( ! isBaseEnvironment( ) )
1698     {
1699       {
1700         IdMap tmp;
1701         bindings_->dumpMap( & tmp );
1702         for( IdMap::const_iterator i = tmp.begin( ); i != tmp.end( ); ++i ){
1703           shadowed->insert( shadowed->begin( ), i->first );
1704         }
1705       }
1706       {
1707         IdMap tmp;
1708         stateBindings_->dumpMap( & tmp );
1709         for( IdMap::const_iterator i = tmp.begin( ); i != tmp.end( ); ++i ){
1710           shadowedStates->insert( shadowedStates->begin( ), i->first );
1711         }
1712       }
1713       depth = parent_->recursivePrint( os, shadowed, shadowedStates ) + 1;
1714     }
1715
1716   std::string indentation = std::string( depth, ' ' );
1717
1718   size_t width = 1;
1719   for( size_t tmp = bindings_->size( ); tmp >= 10; tmp /= 10, ++width )
1720     ;
1721
1722   {
1723     size_t tmp = ( 29 - 4 ) - strlen( debugName_ );
1724     if( tmp < 2 || tmp > 29 ) /* the latter case corresponds to an underflow in the subtraction */
1725       {
1726         tmp = 2;
1727       }
1728     os << indentation << std::string( tmp / 2, '-' ) << "( " << debugName_ << " )" << std::string( tmp - tmp / 2, '-' ) << std::endl ;
1729   }
1730   if( ! isBaseEnvironment( ) )
1731     {
1732       {
1733         IdMap tmp;
1734         bindings_->dumpMap( & tmp );
1735         for( IdMap::const_iterator i = tmp.begin( ); i != tmp.end( ); ++i ){
1736           os << indentation << std::setw(width) << i->second ;
1737           if( shadowedBefore.find( i->first ) != shadowedBefore.end( ) )
1738             {
1739               os << "^" ;
1740             }
1741           else
1742             {
1743               os << " " ;
1744             }
1745           os << " " ;
1746           i->first.show( os, Ast::Identifier::VARIABLE );
1747           os << " : " ;
1748           if( (*values_)[ i->second ] == NullPtr< Kernel::Variable >( ) )
1749             {
1750               os << "< Uninitialized >" ;
1751             }
1752           else if( (*values_)[ i->second ]->isThunk( ) )
1753             {
1754               os << "< thunk >" ;
1755             }
1756           else if( dynamic_cast< const Lang::Instance * >( (*values_)[ i->second ]->getUntyped( ).getPtr( ) ) == NULL )
1757             {
1758               (*values_)[ i->second ]->getUntyped( )->show( os );
1759             }
1760           else
1761             {
1762               os << "..." ;
1763             }
1764           os << std::endl ;
1765         }
1766       }
1767       {
1768         IdMap tmp;
1769         stateBindings_->dumpMap( & tmp );
1770         for( IdMap::const_iterator i = tmp.begin( ); i != tmp.end( ); ++i ){
1771           os << indentation << std::setw(width) << i->second ;
1772           if( shadowedStatesBefore.find( i->first ) != shadowedStatesBefore.end( ) )
1773             {
1774               os << "^" ;
1775             }
1776           else
1777             {
1778               os << " " ;
1779             }
1780           os << " " ;
1781           i->first.show( os, Ast::Identifier::STATE );
1782           os << " :: " ;
1783           if( (*states_)[ i->second ] == NullPtr< Kernel::State >( ) )
1784             {
1785               os << "< Uninitialized >" ;
1786             }
1787           else
1788             {
1789               os << (*states_)[ i->second ]->getTypeName( ) ;
1790             }
1791           os << std::endl ;
1792         }
1793       }
1794     }
1795   else
1796     {
1797       os << indentation << "<< global env >>" << std::endl ;
1798     }
1799
1800   os << indentation << "-- -- -- -- -- -- -- -- -- --" << std::endl ;
1801
1802   return depth;
1803 }