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