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