source/namespacedirectory.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 2015 Henrik Tidefelt
  17  */
  18
  19 #include "namespacedirectory.h"
  20 #include "shapesexceptions.h"
  21 #include "namespacescanner.h"
  22 #include "shapesscanner.h"
  23 #include "ptrowner.h"
  24 #include "globals.h"
  25
  26 #include <fstream>
  27 #include <queue>
  28 #include <dirent.h>
  29 #include <libgen.h>
  30
  31 using namespace Shapes;
  32
  33
  34 Ast::NamespaceDeclarations::NamespaceDeclarations( )
  35 : encapsulated_( false )
  36 { }
  37
  38 void
  39 Ast::NamespaceDeclarations::addPrelude( const std::string & entry )
  40 {
  41   preludeSet_.insert( preludeSet_.begin( ), entry );
  42 }
  43
  44 void
  45 Ast::NamespaceDeclarations::addIgnore( const std::string & entry )
  46 {
  47   ignoreSet_.insert( ignoreSet_.begin( ), entry );
  48 }
  49
  50 void
  51 Ast::NamespaceDeclarations::addPrecedes( const std::set< std::string > & x, const std::set< std::string > & y )
  52 {
  53   for( std::set< std::string >::const_iterator i = x.begin(); i != x.end(); ++i ){
  54     std::set< std::string > & s = orderGraph_[ *i ];
  55     s.insert( y.begin( ), y.end( ) );
  56   }
  57 }
  58
  59 class OrderGraphNode
  60 {
  61   std::list< OrderGraphNode * > predecessors_;
  62   Ast::NamespaceDirectoryEntry * entry_;
  63   bool visited_;
  64 public:
  65   OrderGraphNode( Ast::NamespaceDirectoryEntry * entry )
  66   : entry_( entry ), visited_( false )
  67   { }
  68   void addPredecessor( OrderGraphNode * pre )
  69   {
  70     predecessors_.push_back( pre );
  71   }
  72   bool visited( ) const { return visited_; }
  73   std::string name( ) const { return entry_->name( ); }
  74   /* Returns NULL if no cycle was detected.
  75    * Otherwise, a pointer to a node on a cycle is returned.
  76    */
  77   OrderGraphNode * depthFirstVisit( std::stack< Ast::NamespaceDirectoryEntry * > * loadOrderStack )
  78   {
  79     if( visited_ ){
  80       return this;
  81     }
  82     visited_ = true;
  83
  84     typedef typeof predecessors_ ListType;
  85     for( ListType::iterator i = predecessors_.begin( ); i != predecessors_.end( ); ++i ){
  86       OrderGraphNode * cycleNode = (*i)->depthFirstVisit( loadOrderStack );
  87       if( cycleNode != NULL )
  88         return cycleNode;
  89     }
  90
  91     loadOrderStack->push( entry_ );
  92
  93     return NULL;
  94   }
  95 };
  96
  97 void
  98 Ast::NamespaceDeclarations::invalidOrderGraphEntries( const std::map< std::string, NamespaceDirectoryEntry * > & entries, std::set< std::string > * invalidEntries ) const
  99 {
 100   typedef typeof orderGraph_ OrderMapType;
 101   for( OrderMapType::const_iterator i = orderGraph_.begin( ); i != orderGraph_.end( ); ++i ){
 102     invalidEntries->insert( invalidEntries->begin( ), i->first );
 103     invalidEntries->insert( i->second.begin( ), i->second.end( ) );
 104   }
 105   typedef typeof entries EntriesMapType;
 106   for( EntriesMapType::const_iterator i = entries.begin( ); i != entries.end( ); ++i ){
 107     invalidEntries->erase( i->first );
 108   }
 109 }
 110
 111
 112 std::string
 113 Ast::NamespaceDeclarations::orderEntries( const std::map< std::string, NamespaceDirectoryEntry * > & entries, std::vector< NamespaceDirectoryEntry * > * loadOrder ) const
 114 {
 115   PtrOwner_back_Access< std::list< OrderGraphNode * > > nodeMemory;
 116   typedef std::map< std::string, OrderGraphNode * > NodeMap;
 117   NodeMap nodes;
 118   typedef typeof entries EntriesMapType;
 119   for( EntriesMapType::const_iterator i = entries.begin( ); i != entries.end( ); ++i ){
 120     OrderGraphNode * node = new OrderGraphNode( i->second );
 121     nodeMemory.push_back( node );
 122     nodes[ i->first ] = node;
 123   }
 124
 125   for( NodeMap::const_iterator i = nodes.begin( ); i != nodes.end( ); ++i ){
 126     typedef typeof orderGraph_ OrderMapType;
 127     OrderMapType::const_iterator j = orderGraph_.find( i->first );
 128     if( j == orderGraph_.end( ) )
 129       continue;
 130     typedef typeof j->second SetType;
 131     for( SetType::const_iterator k = j->second.begin( ); k != j->second.end( ); ++j ){
 132       NodeMap::iterator l = nodes.find( *k );
 133       if( l == nodes.end( ) ){
 134         throw Exceptions::InternalError( "Ast::NamespaceDeclarations::orderEntries: Invalid entries should have been detected earlier." );
 135       }
 136       i->second->addPredecessor( l->second );
 137     }
 138   }
 139
 140   std::stack< Ast::NamespaceDirectoryEntry * > loadOrderStack;
 141   for( NodeMap::iterator i = nodes.begin( ); i != nodes.end( ); ++i ){
 142     OrderGraphNode * node = i->second;
 143     if( node->visited( ) )
 144       continue;
 145     OrderGraphNode * cycleNode = node->depthFirstVisit( & loadOrderStack );
 146     if( cycleNode != NULL )
 147       return cycleNode->name( );
 148   }
 149
 150   loadOrder->clear( );
 151   loadOrder->reserve( entries.size( ) );
 152   while( ! loadOrderStack.empty( ) ){
 153     loadOrder->push_back( loadOrderStack.top( ) );
 154     loadOrderStack.pop( );
 155   }
 156
 157   return std::string( );
 158 }
 159
 160
 161 Ast::NamespaceDirectoryEntry::NamespaceDirectoryEntry( const std::string & name, const Ast::NamespaceDirectory * parent )
 162 : name_( name ), parent_( parent ), prelude_( false )
 163 { }
 164
 165 Ast::NamespaceDirectoryEntry::~NamespaceDirectoryEntry( )
 166 { }
 167
 168 void
 169 Ast::NamespaceDirectoryEntry::schedulePrelude( Ast::LoadStack * loadStack )
 170 {
 171   this->schedule_impl( loadStack, true );
 172 }
 173
 174 void
 175 Ast::NamespaceDirectoryEntry::schedule( Ast::LoadStack * loadStack )
 176 {
 177   this->schedule_impl( loadStack, false );
 178 }
 179
 180
 181 Ast::NamespaceDirectory::NamespaceDirectory( const RefCountPtr< const Ast::NamespacePath > & namespacePath, const std::string & filesystemPath, const std::string & name, const Ast::NamespaceDirectory * parent )
 182   : Ast::NamespaceDirectoryEntry( name, parent ), initialized_( false ), namespacePath_( namespacePath ), filesystemPath_( filesystemPath ), encapsulated_( false )
 183 { }
 184
 185 Ast::NamespaceDirectory::~NamespaceDirectory( )
 186 { }
 187
 188 void
 189 Ast::NamespaceDirectory::schedule_impl( Ast::LoadStack * loadStack, bool preludeOnly )
 190 {
 191   initialize( );
 192
 193   typedef typeof loadOrder_ VecType;
 194   for( VecType::iterator i = loadOrder_.begin( ); i != loadOrder_.end( ); ++i ){
 195     if( preludeOnly && ! (*i)->prelude( ) )
 196       continue;
 197     (*i)->schedule_impl( loadStack, preludeOnly );
 198   }
 199 }
 200
 201 void
 202 Ast::NamespaceDirectory::scheduleNamespace( const Ast::NamespacePath & namespacePath, const Ast::NamespacePath::const_iterator & nsBegin, Ast::LoadStack * loadStack )
 203 {
 204   initialize( );
 205
 206   if( nsBegin == namespacePath.end( ) ){
 207     schedule( loadStack );
 208     return;
 209   }
 210
 211   Ast::NamespacePath::const_iterator next( nsBegin );
 212   ++next;
 213
 214   typedef typeof entries_ MapType;
 215   MapType::iterator i = entries_.find( *nsBegin );
 216   if( i == entries_.end( ) ){
 217     throw Exceptions::NamespaceDirectoryLookupError( Exceptions::NamespaceDirectoryLookupError::NOT_FOUND, namespacePath.begin( ), next );
 218   }
 219
 220   NamespaceDirectory * dir = dynamic_cast< NamespaceDirectory * >( i->second );
 221   if( dir == NULL ){
 222     throw Exceptions::NamespaceDirectoryLookupError( Exceptions::NamespaceDirectoryLookupError::WRONG_TYPE, namespacePath.begin( ), next );
 223   }
 224
 225   dir->scheduleNamespace( namespacePath, next, loadStack );
 226 }
 227
 228 const Ast::FileID *
 229 Ast::NamespaceDirectory::resolveSingleFile( const Ast::NamespacePath & namespacePath, const Ast::NamespacePath::const_iterator & nsBegin, const std::string & filename, const Ast::SourceLocation & loc )
 230 {
 231   initialize( );
 232
 233   if( nsBegin == namespacePath.end( ) ){
 234
 235     typedef typeof entries_ MapType;
 236     MapType::iterator i = entries_.find( filename );
 237     if( i == entries_.end( ) ){
 238       throw Exceptions::NamespaceDirectoryFileError( loc, Exceptions::NamespaceDirectoryFileError::NOT_FOUND, namespacePath, filename );
 239     }
 240
 241     NamespaceFile * fileEntry = dynamic_cast< NamespaceFile * >( i->second );
 242     if( fileEntry == NULL ){
 243       throw Exceptions::NamespaceDirectoryFileError( loc, Exceptions::NamespaceDirectoryFileError::WRONG_TYPE, namespacePath, filename );
 244     }
 245
 246     return fileEntry->fileID();
 247
 248   }
 249
 250   Ast::NamespacePath::const_iterator next( nsBegin );
 251   ++next;
 252
 253   typedef typeof entries_ MapType;
 254   MapType::iterator i = entries_.find( *nsBegin );
 255   if( i == entries_.end( ) ){
 256     throw Exceptions::NamespaceDirectoryLookupError( loc, Exceptions::NamespaceDirectoryLookupError::NOT_FOUND, namespacePath.begin( ), next );
 257   }
 258
 259   NamespaceDirectory * dir = dynamic_cast< NamespaceDirectory * >( i->second );
 260   if( dir == NULL ){
 261     throw Exceptions::NamespaceDirectoryLookupError( loc, Exceptions::NamespaceDirectoryLookupError::WRONG_TYPE, namespacePath.begin( ), next );
 262   }
 263
 264   return dir->resolveSingleFile( namespacePath, next, filename, loc );
 265 }
 266
 267 std::string
 268 Ast::NamespaceDirectory::name( ) const
 269 {
 270   return filesystemPath_;
 271 }
 272
 273 void
 274 Ast::NamespaceDirectory::initialize( )
 275 {
 276   if( initialized_ )
 277     return;
 278   initialized_ = true;
 279
 280   std::string filename = Ast::theShapesScanner.needpathWithSuffix( filesystemPath_ + "/", "Shapes-Namespace.txt" );
 281   std::ifstream iFile( filename );
 282   struct stat iFileStat;
 283   if( stat( filename.c_str( ), & iFileStat ) != 0 || ! iFile.is_open( ) ){
 284     throw Exceptions::FileReadOpenError( Ast::THE_UNKNOWN_LOCATION, strrefdup( filename ), NULL, NULL );
 285   }
 286   const Ast::FileID * iFileID = Ast::FileID::build_stat( iFileStat, filename );
 287
 288   NamespaceDeclarations declarations;
 289   NamespaceScanner scanner( & declarations, & iFile, iFileID );
 290   int status = scanner.yylex( );
 291   if( status != 0 )
 292     {
 293       std::ostringstream oss;
 294       oss << "Namespace scanner returned with non-zero status: " << status ;
 295       throw Exceptions::InternalError( strrefdup( oss ) );
 296     }
 297
 298   encapsulated_ = declarations.encapsulated( );
 299
 300   DIR* deDir = opendir( filesystemPath_.c_str( ) );
 301   if( deDir == NULL ){
 302     throw Exceptions::FileReadOpenError( Ast::THE_UNKNOWN_LOCATION, strrefdup( filesystemPath_ ), NULL, NULL );
 303   }
 304
 305   for( struct dirent* de = readdir(deDir); de != NULL; de = readdir(deDir) ) {
 306     if (strcmp(de->d_name, ".") == 0 || strcmp(de->d_name, "..") == 0)
 307       continue;
 308     std::string name( de->d_name );
 309     if( declarations.inIgnoreSet( name ) )
 310       continue;
 311     std::string fullname = filesystemPath_ + "/" + name;
 312     struct stat theStat;
 313     if( stat( fullname.c_str( ), & theStat ) != 0 )
 314       continue; /* Strange directory entry, ignore it. */
 315     if( ( theStat.st_mode & S_IFDIR ) != 0 ){
 316       addDirectory( name, fullname, declarations.inPreludeSet( name ) );
 317     }else if( ( theStat.st_mode & S_IFREG ) != 0 ){
 318       if( name.compare( name.size( ) - 6, std::string::npos, ".shext" ) == 0 ){
 319         const Ast::FileID * fileID = Ast::FileID::build_stat( theStat, fullname );
 320         NamespaceFile * entry = new NamespaceFile( fileID, name, this );
 321         if( declarations.inPreludeSet( name ) )
 322           entry->setPrelude( );
 323         entries_[ name ] = entry;
 324       }
 325     }else{
 326       /* Other type of file, ignore it. */
 327     }
 328   }
 329   closedir( deDir );
 330
 331   std::set< std::string > invalidEntries;
 332   declarations.invalidOrderGraphEntries( entries_, & invalidEntries );
 333   if( ! invalidEntries.empty( ) ){
 334     throw Exceptions::NamespaceDirectoryInvalidEntries( namespacePath_, invalidEntries );
 335   }
 336
 337   std::string cycleEntry = declarations.orderEntries( entries_, & loadOrder_ );
 338   if( ! cycleEntry.empty( ) ){
 339     throw Exceptions::NamespaceDirectoryCircularOrdering( namespacePath_, cycleEntry );
 340   }
 341 }
 342
 343 bool
 344 Ast::NamespaceDirectory::addDirectory( const std::string & nsName, const std::string & dir, bool prelude )
 345 {
 346   std::string filename = Ast::theShapesScanner.needpathWithSuffix( dir + "/", "Shapes-Namespace.txt" );
 347   std::ifstream iFile( filename );
 348   if( ! iFile.is_open( ) )
 349     return false;
 350
 351   typedef typeof entries_ MapType;
 352   MapType::iterator i = entries_.find( nsName );
 353   if( i != entries_.end( ) ){
 354     throw Exceptions::AmbiguousNamespaceDirectory( i->second->name( ), dir );
 355   }
 356
 357   Ast::NamespacePath * pathMem = new Ast::NamespacePath( *namespacePath_ );
 358   RefCountPtr< const Ast::NamespacePath > path( pathMem );
 359   /* Leaking memory with each strdup below, see 'Memory management notice' in identifier.h. */
 360   if( encapsulated_ )
 361     pathMem->push_back( strdup( Ast::theShapesScanner.newEncapsulationName( ).getPtr( ) ) );
 362   pathMem->push_back( strdup( nsName.c_str( ) ) );
 363   NamespaceDirectory * entry = new NamespaceDirectory( path, dir, nsName, this );
 364   if( prelude )
 365     entry->setPrelude( );
 366   entries_[ nsName ] = entry;
 367
 368   return true;
 369 }
 370
 371
 372 Ast::NamespaceFile::NamespaceFile( const FileID * fileID, const std::string & name, const Ast::NamespaceDirectory * parent )
 373   : Ast::NamespaceDirectoryEntry( name, parent), fileID_( fileID )
 374 { }
 375
 376 Ast::NamespaceFile::~NamespaceFile( )
 377 { }
 378
 379 void
 380 Ast::NamespaceFile::schedule_impl( Ast::LoadStack * loadStack, bool preludeOnly )
 381 {
 382   if( ! prelude_ && preludeOnly ){
 383     throw Exceptions::InternalError( "Ast::NamespaceFile::schedule was called on a non-prelude file while loading the prelude." );
 384   }
 385   loadStack->push( fileID_, parent_->namespacePath( ) );
 386 }
 387
 388 std::string
 389 Ast::NamespaceFile::name( ) const
 390 {
 391   return fileID_->name( );
 392 }
 393
 394
 395 Ast::LoadStack::LoadStack( )
 396 { }
 397
 398 void
 399 Ast::LoadStack::push( const FileID * fileID, const RefCountPtr< const Ast::NamespacePath > & namespacePath )
 400 {
 401   fileIDs_.push( fileID );
 402   namespacePaths_.push( namespacePath );
 403 }
 404
 405 void
 406 Ast::LoadStack::pop( )
 407 {
 408   fileIDs_.pop( );
 409   namespacePaths_.pop( );
 410 }
 411
 412
 413
 414
 415 Ast::NamespaceLoader::NamespaceLoader( )
 416 { }
 417
 418 Ast::NamespaceLoader::~NamespaceLoader( )
 419 {
 420   typedef typeof topEntries_ MapType;
 421   for( MapType::iterator i = topEntries_.begin( ); i != topEntries_.end( ); ++i ){
 422     delete i->second;
 423   }
 424 }
 425
 426 void
 427 Ast::NamespaceLoader::registerNeedDirectory( const std::string & dir )
 428 {
 429   struct stat theStat;
 430   if( stat( dir.c_str( ), & theStat ) != 0 )
 431     return;
 432   if( ( theStat.st_mode & S_IFDIR ) == 0 ){
 433     /* Ignore non-directory */
 434     return;
 435   }
 436
 437   /* See if the directory itself is a namespace directory. */
 438   {
 439     char* dirstr = strdup( dir.c_str( ) );
 440     std::string nsName( basename( dirstr ) );
 441     free(dirstr);
 442     if( addDirectory( nsName, dir ) )
 443       return;
 444   }
 445
 446   /* See if any of the subdirectories are namespace directories. */
 447   DIR* deDir = opendir( dir.c_str( ) );
 448   while (deDir != NULL) {
 449     struct dirent* de = readdir(deDir);
 450     if (de == NULL) break;
 451     if (strcmp(de->d_name, ".") == 0 || strcmp(de->d_name, "..") == 0)
 452       continue;
 453     std::string nsName( de->d_name );
 454     std::string subdir = dir + "/" + nsName;
 455     if( stat( subdir.c_str( ), & theStat ) != 0 )
 456       continue; /* Strange directory entry, ignore it. */
 457     if( ( theStat.st_mode & S_IFDIR ) == 0 )
 458       continue;
 459     addDirectory( nsName, subdir );
 460   }
 461   closedir( deDir );
 462 }
 463
 464 bool
 465 Ast::NamespaceLoader::addDirectory( const std::string & nsName, const std::string & dir )
 466 {
 467   std::string filename = Ast::theShapesScanner.needpathWithSuffix( dir + "/", "Shapes-Namespace.txt" );
 468   std::ifstream iFile( filename );
 469   if( ! iFile.is_open( ) )
 470     return false;
 471
 472   typedef typeof topEntries_ MapType;
 473   MapType::iterator i = topEntries_.find( nsName );
 474   if( i != topEntries_.end( ) ){
 475     throw Exceptions::AmbiguousNamespaceDirectory( i->second->name( ), dir );
 476   }
 477
 478   Ast::NamespacePath * pathMem = new Ast::NamespacePath( );
 479   RefCountPtr< const Ast::NamespacePath > path( pathMem );
 480   pathMem->push_back( strdup( nsName.c_str( ) ) ); /* Leaking memory, see 'Memory management notice' in identifier.h. */
 481   topEntries_[ nsName ] = new NamespaceDirectory( path, dir, nsName, NULL );
 482
 483   return true;
 484 }
 485
 486 void
 487 Ast::NamespaceLoader::pushPreludeFiles( LoadStack * loadStack )
 488 {
 489   typedef typeof topEntries_ MapType;
 490   for( MapType::iterator i = topEntries_.begin( ); i != topEntries_.end( ); ++i ){
 491     i->second->schedulePrelude( loadStack ); /* true means to only schedule the prelude. */
 492   }
 493 }
 494
 495 void
 496 Ast::NamespaceLoader::pushNamespaceFiles( const Ast::NamespacePath & namespacePath, LoadStack * loadStack )
 497 {
 498   if( namespacePath.empty() ){
 499     throw Exceptions::NamespaceDirectoryLookupError( Exceptions::NamespaceDirectoryLookupError::GLOBAL, namespacePath.begin( ), namespacePath.end( ) );
 500   }
 501
 502   Ast::NamespacePath::const_iterator begin = namespacePath.begin( );
 503   Ast::NamespacePath::const_iterator next = begin;
 504   ++next;
 505
 506   typedef typeof topEntries_ MapType;
 507   MapType::iterator i = topEntries_.find( *begin );
 508   if( i == topEntries_.end( ) ){
 509     throw Exceptions::NamespaceDirectoryLookupError( Exceptions::NamespaceDirectoryLookupError::NOT_FOUND, namespacePath.begin( ), next );
 510   }
 511
 512   i->second->scheduleNamespace( namespacePath, next, loadStack );
 513 }
 514
 515 const Ast::FileID *
 516 Ast::NamespaceLoader::resolveSingleFile( const Ast::NamespacePath & namespacePath, const std::string & filename, const Ast::SourceLocation & loc )
 517 {
 518   if( namespacePath.empty() ){
 519     throw Exceptions::NamespaceDirectoryLookupError( loc, Exceptions::NamespaceDirectoryLookupError::GLOBAL, namespacePath.begin( ), namespacePath.end( ) );
 520   }
 521
 522   Ast::NamespacePath::const_iterator begin = namespacePath.begin( );
 523   Ast::NamespacePath::const_iterator next = begin;
 524   ++next;
 525
 526   typedef typeof topEntries_ MapType;
 527   MapType::iterator i = topEntries_.find( *begin );
 528   if( i == topEntries_.end( ) ){
 529     throw Exceptions::NamespaceDirectoryLookupError( loc, Exceptions::NamespaceDirectoryLookupError::NOT_FOUND, namespacePath.begin( ), next );
 530   }
 531
 532   return i->second->resolveSingleFile( namespacePath, next, filename, loc );
 533 }