include/EDoc/Dictionary.h

Go to the documentation of this file.

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

   Copyright (C) 2007 by Brendon Costa

   This library is free software; you can redistribute it and/or modify 
   it under the terms of the "LGPL Like" License defined in the file COPYING 
   that should have been distributed along with this source.

   This library is distributed in the hope that it will be useful, 
   but WITHOUT ANY WARRANTY; without even the implied warranty of 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  

   You should have received a copy of the "LGPL Like" License 
   along with this library; see the file COPYING. if not, it can be 
   obtained from the EDoc++ website: 
   http://edoc.sourceforge.net/license.html

*******************************************************************************/
#ifndef EDOC_DICTIONARY_H
#define EDOC_DICTIONARY_H

#include "EDoc/PropogatingException.h"
#include "EDoc/exceptions.h"
#include "EDoc/ProgressIFace.h"
#include "EDoc/StringIdentifiedObject.h"
#include "EDoc/TranslationUnit.h"
#include "EDoc/SpecificManagedObject.h"

#include <string>
#include <map>
#include <ostream>
#include <vector>
#include <list>
#include <sstream>



namespace EDoc
{
   class PersistenceIFace;
   class Type;
   class Function;
   class File;
   class CodeBlock;
   class CatchBlock;
   class TryBlock;
   class FunctionType;
   
   //===========================================================================
   /** \brief Represents one or more merged translation units.
    *
    * The Dictionary class is the main class of the system. Dictionary objects
    * have 1:1 mappings with .edc files. You will read a .edc file into a
    * dictionary instance or write one from a Dictionary instance.
    *
    * Most objects belong to a specific dictionary. This is important for
    * correct memory management. It is not possible to assign pointers to
    * DictionarySpecific objects between different dictionary instances.
    *
    * The main object types directly stored in a Dictionary include:
    *
    *    - File : Represents a source file used in compiling some 
    *       code (Headers too).
    *    - Type : Represents a C/C++ type like integers, floats, classes etc.
    *    - FunctionType : This is used to represent C/C++ function types. They
    *       are stored seperate from normal types as they are "conglomerate"
    *       types made up from a number of Type objects. 
    *    - Function : These represent individual functions in a compiled binary.
    *    .
    *
    * These above object types are specially managed. In order to simplify the
    * memory allocation and handling of these objects, we have made them all
    * derive from the StringIdentifiedObject class. Each of these objects is
    * identified by a unique string. For example a Function is identified by the
    * string for the name used as its link name which you would see using nm on
    * a binary file.
    *
    * It is helpful to note that while these objects are all identified by
    * unique string keys, in the .edc files they are identified by integer
    * indexes. This makes the loading procedure become a two stage procedure
    * and the IndexedDictionary is used to perform the initial load using
    * indexes. Using integer indexes in the .edc files was done to decrease
    * loading/saving times and to decrease file size. See Read() and Write() for
    * more information.
    *
    * Most objects in EDoc are DictionarySpecific objects. This means that
    * they are associated with a particular dictionary. These object can NOT be
    * referenced from objects within a different dictionary but must be
    * duplicated to the other dictionary first before they can be referenced by
    * any objects in the other dictionary. This can often be achieved using code
    * like follows:
    *
    * \code
    *    void Func(Type* other_dict_type)
    *    {
    *       // Will retrieve or create the type from this dictionary with the
    *       // same string identifier as the type from the other dictionary.
    *       // However the type will be "empty" if it did not exist in this
    *       // dictionary to start with.
    *       Type* this_dict_type = this_dict.types.AlwaysGet(*other_dict_type);
    *    }
    * \endcode
    *
    * If the type is not complete then its IsPopulated() will return
    * false. In which case you will need to populate it using the assignment
    * operator or some other means. Also note however that when populating it
    * the type may also referr to other "un-populated" objects that you will
    * need to populate. 
    *
    * As you can see it is not easy to move or copy objects from one dictionary
    * to another. Most usages of the EDoc however will not require the user to
    * do anything like this anyhow as all the assigning/merging etc is done by
    * the procedure of:
    *
    * dict1.Read(...);
    * dict2.Read(...);
    * dict1.Merge(dict2);
    *
    * This will read two .edc files into two seperate dictionaries, and then
    * "merge" the two dictionaries. A merge is kind of like linking
    * objects/libraries together in the development of an application.
    *
    * Temporary Dictionary Staging Area
    *
    * When using the EDoc python module, you will probably make use of the
    * temporary dictionary staging area. This is a static pointer to a "current"
    * working dictionary. This will generally be used for communication between
    * the python and C++ code. In particular the python wrappers require the use
    * of a default constructor for most data types due to a limitation (OR I
    * JUST DONT KNOW HOW TO USE IT PROPERLY YET) of Swig. Since most objects
    * require that the dictionary that they will belong to be passed upon
    * construction time, this means that there is no real possibility of having
    * a default constructor. Instead now, if the default constructor is used,
    * all DictionarySpecific objects will use the dictionary that can be
    * currently retrieved using GetCurrentDictionaryAssert()
    *
    * See GetCurrentDictionary() for more details.
    */
   class Dictionary
   {
   public:

      //------------------------------------------------------------------------
      /** \brief Constructor.
       *
       * Note: Will create a single File object called UNKNOWN_FILE and also
       * a single location object called UNKNOWN_LOCATION. These will exist in
       * all dictionaries.
       */
      Dictionary();

      //------------------------------------------------------------------------
      /** \brief Erases all memory for all objects that are specific to this
       * dictionary.
       *
       * This will erase all DictionarySpecific objects owned
       * by this dictionary.
       */
      ~Dictionary();

      //------------------------------------------------------------------------
      /** \brief Reads the contents of a .edc file into this dictionary
       * instance.
       *
       * This will replace the contents of this dictionary with the contents of
       * the .edc file. All old state of this dictionary will be lost.
       *
       * The process of reading .edc files is quite involved. It is mostly made
       * so by certain limitations placed on it by the GCC modification and also
       * due to the design decision of storing references to objects in the .edc
       * file using integer indexes instead of string keys as are using in the
       * runtime objects.
       *
       * When a read operation occurs the following sequence is followed:
       *    -# Erase all current data from the dictionary.
       *    -# Construct an Indexed dictionary used to associate integer index
       *       references with object instances.
       *    -# Read the contents of the .edc file header. This includes info
       *       like translation units referenced in .edc file, version
       *       information etc.
       *    -# Read all data records.
       *    -# Validate that all read data objects have been inserted into the
       *       dictionary.
       *    .
       *
       * The IndexedDictionary is used to associated particular instances with
       * indexes as they are read from the file. 
       *
       * reading of data objects occurs in a a set number of stages. These
       * stages correspond to the indexes of items in the managed objects
       * vector. I.e.
       *
       *    -# Stage 0: File objects         : GetManagedObjectsVector() index 0
       *    -# Stage 1: Type objects         : GetManagedObjectsVector() index 1
       *    -# Stage 2: FunctionType objects : GetManagedObjectsVector() index 2
       *    -# Stage 3: Function objects     : GetManagedObjectsVector() index 3
       *    .
       *
       * Doing the stages this way GREATLY simplifies the reading code as it is
       * the same for each data object type except the index to the vector
       * changes as you move from one stage to the next.
       *
       * This places the requirement on the .edc files that all items must be
       * saved to the file in the given order: File, Type, FunctionType,
       * Function
       */
      void Read(PersistenceIFace& file);

      //------------------------------------------------------------------------
      /** \brief Writes the contents of this dictionary to a .edc file.
       *
       * Writing is a simple task in comparison to reading. It simply assigns 
       * an integer index to each object before writing. Writes all objects and
       * then resets the integer indexes to -1.
       */
      void Write(PersistenceIFace& file) const;

      //------------------------------------------------------------------------
      /** \brief Merges the contents of another dictionary into this dictionary.
       *
       * This is similar to linking objects together. It will resolve calls to
       * un-implemented functions with the correct implementations from other
       * translation units. It will produce errors if multiple implementations
       * are found of a single function (If they are different so we dont emit
       * errors for "vaguely" linked functions). 
       *
       * The result is a modified Dictionary that is the union of the two.
       */
      void Merge(const Dictionary& right);

      //------------------------------------------------------------------------
      /** \brief Replaces all references of pointer remove with pointer replace.
       *
       * This is used during the loading process to remove duplicate objects
       * from all dictionary specific objects and replace them with a single
       * "reference" object. After calling this function the user can be
       * guarenteed that this object will no longer contain any references to
       * "remove".
       *
       * When used on a dictionary this will attempt to replace all references
       * to the pointer remove over the entire Dictionary instance andall its
       * children.
       *
       * \param stack Is a processing stack used to ensure that recursive
       * associations do not form endless loops of replacing.
       *
       * \param remove Is a pointer value that we wish to replace.
       *
       * \param replace Is a pointer value to replace all instances of remove
       * with.
       *
       * \return Returns the number of occurences of remove that were replaced
       * with replace.
       */
      size_t ReplaceReferences(PStack& stack, void* remove, void* replace);

      //------------------------------------------------------------------------
      /** \brief Prints the contents of this object to the given stream in a
       * user readable manner.
       *
       * \param out The output stream to print to.
       *
       * \param prefix A prefix to print before every line displayed. Usually
       * used to provide indenting when printing a heirarchy of objects.
       */
      std::ostream& Print(std::ostream& out, std::string prefix="") const;

      //------------------------------------------------------------------------
      /** \brief Returns a string with the same contents as would be displayed
       * by the Print() function.
       */
      std::string ToString(std::string prefix="") const;

      //------------------------------------------------------------------------
      /** \brief Performs internal validation of the Dictionary object and all
       * its data.
       *
       * This will raise a BugException if internal validation fails andshould
       * only be used for debugging purposes. It is quite slow.
       */
      void Validate() const;


      //------------------------------------------------------------------------
      // Calculation of propogating exceptions.
      //------------------------------------------------------------------------

      //------------------------------------------------------------------------
      /** \brief Expands FunctionPointer calls and Virtual function calls into
       * a list of "possible" function calls.
       *
       * This results in a "more than complete" call-graph.
       *
       * \see See CalculatePropogatingExceptions() for information about 
       * this group of functions.
       */
      void ExpandCallGraph();

      //------------------------------------------------------------------------
      /** \brief Erases all propogating exception data from all functions.
       *
       * This must be called before calculating the propogating exception 
       * information to ensure it starts with a clean slate.
       *
       * \see See CalculatePropogatingExceptions() for information about 
       * this group of functions.
       */
      void ErasePropogatingExceptions();

      //------------------------------------------------------------------------
      /** \brief Analyses the callgraph of all functions ordering them 
       * by complexity and marking circular callgraphs.
       *
       * This will mark the complexity of a function by setting: 
       * Function::total_calls to the number of unique functions called.
       * It will also identify circular callgraphs between a group of functions
       * and if such exists will create the member: Function::circular
       * with a set of the functions in the circular graph.
       *
       * Finally it will return a vector of all the functions sorted in
       * order of their Function::total_calls member. This is used to process
       * the functions in order when calculating the propogating exceptions
       * In particular it is dynamic programming in action. By calculating the
       * least complex functions first, they are then available to be used
       * in the more complex functions later. I.e. The processing the functions
       * in this order means that we dont need to "re-calculate" information.
       * 
       *
       * \see See CalculatePropogatingExceptions() for information about 
       * this group of functions.
       */
      void CalculateCallComplexity(std::vector <Function*>& funcs);

      //------------------------------------------------------------------------
      /** \brief Calculates the propogating exceptions for all functions
       * provided in the vector sorted which must be in order of the call 
       * complexity.
       *
       * This function asserts that the vector is provided in the correct order.
       *
       * To calculate the propogating exceptions for a dictionary
       * the following functions must be called in order:
       *
       *    -# ExpandCallGraph()
       *    -# ErasePropogatingExceptions()
       *    -# CalculateCallComplexity()
       *    -# CalculatePropogatingExceptions()
       *    .
       *
       * This function makes use of:
       *    - GenerateExceptions()
       *    - HandleCircularCallgraph(
       *    - PostProcessExceptions()
       *    - ProcessFunction()
       *    - ProcessCodeBlock()
       *    - ProcessTryBlock()
       *    .
       *
       * \todo Document the algorithm used for this operation.
       */
      void CalculatePropogatingExceptions(std::vector <Function*>& sorted,
         FunctionProgressIFace* progress = NULL);


      //------------------------------------------------------------------------
      /** \brief Returns the translation unit with the given index.
       */
      TranslationUnit* GetIndexedTranslationUnit(int32_t index);

      //------------------------------------------------------------------------
      /** \brief Returns the index of the provided translation unit.
       *
       * NOTE: Will throw a BugException if the translation unit is not in this
       * dictionaries list of translation units.
       */
      int32_t GetTranslationUnitIndex(TranslationUnit* tu);

      //------------------------------------------------------------------------
      /** \brief Returns a list containing a reference to the ManagedObject
       * types being managed by this dictionary.
       *
       * This includes all File, Type, FunctionType and Function instances.
       */
      inline std::list<ManagedObjectPtr> GetManagedObjects()
      {
         // NOTE: The order of this list is important and MUST be the same order
         // in which we expect to load the various record types from the file.
         std::list<ManagedObjectPtr> ret;
         ret.push_back(&files);
         ret.push_back(&types);
         ret.push_back(&function_types);
         ret.push_back(&functions);
         return ret;
      }

      //------------------------------------------------------------------------
      /** \brief See GetManagedObjects()
       */
      inline std::vector<ManagedObjectPtr> GetManagedObjectsVector()
      {
         // NOTE: The order of this list is important and MUST be the same order
         // in which we expect to load the various record types from the file.
         std::vector<ManagedObjectPtr> ret;
         ret.push_back(&files);
         ret.push_back(&types);
         ret.push_back(&function_types);
         ret.push_back(&functions);
         return ret;
      }

      //------------------------------------------------------------------------
      /** \brief See GetManagedObjects()
       */
      inline std::vector<const ManagedObject*> GetManagedObjectsVector() const
      {
         // NOTE: The order of this list is important and MUST be the same order
         // in which we expect to load the various record types from the file.
         std::vector<const ManagedObject*> ret;
         ret.push_back(&files);
         ret.push_back(&types);
         ret.push_back(&function_types);
         ret.push_back(&functions);
         return ret;
      }




      //------------------------------------------------------------------------
      // Public Data
      //------------------------------------------------------------------------

      //------------------------------------------------------------------------
      /** \brief Every dictionary contains an "Unknown File" pointer that is
       * used for source files we could not determine.
       */
      const File* UNKNOWN_FILE;

      //------------------------------------------------------------------------
      /** \brief Every dictionary contains an "Unknown File" pointer that is
       * used for source locations we could not determine in the GCC MOD.
       */
      const Location* UNKNOWN_LOCATION;

      //------------------------------------------------------------------------
      /** \brief Substitution exceptions type.
       */
      const Type* SUBSTITUTION_EXCEPTION_TYPE;

      SpecificManagedObject<File> files;
      SpecificManagedObject<Type> types;
      SpecificManagedObject<FunctionType> function_types;
      SpecificManagedObject<Function> functions;

      //------------------------------------------------------------------------
      /** \brief A vector of all translation units that have been merged into
       * this dictionary.
       */
      std::vector<TranslationUnit*> translation_units;

      //------------------------------------------------------------------------

   protected:


      //------------------------------------------------------------------------
      /** \brief Erases all data associated with this dictionary instance.
       */
      void EraseAll();

      //------------------------------------------------------------------------
      /** \brief Generates default set of data required by all dictionaries.
       */
      void GeneratePredefined();

      //------------------------------------------------------------------------
      /** \brief Process the given function and functions it calls to generate
       * the list of exceptions that may be emitted by it.
       *
       * This does not return a completed list of propogating exceptions
       * in the case where the function participates in a circular callgraph.
       * In this case the list of exceptions will include one or more exceptions
       * with type: SUBSTITUTION_EXCEPTION_TYPE and the function
       * will return a boolean value of true.
       *
       * In the case of the function participating in a circular
       * callgraph, only the first function in that callgraph should
       * return a value of true. 
       *
       * \return Returns a value of true if this function was part
       * of a circular callgraph AND additional processing needs to be
       * performed on this function (and the others in the callgraph) by
       * the HandleCircularCallgraph) function. I.e. If this function
       * returns true then you must also call HandleCircularCallgraph().
       */
      bool GenerateExceptions(
         FunctionProgressIFace* progress, Function& function);
   
      //------------------------------------------------------------------------
      /** \brief Handles the special case of a circular callgraph
       * when calculating propogating exceptions for a function.
       *
       * This will ensure that GenerateExceptions() has been called
       * for all functions in the circular callgraph. Following this
       * it will then find the union of all exceptions thrown by those
       * functions and then will substitute that unioned list of 
       * exceptions for all exceptions of that have the type:
       * SUBSTITUTION_EXCEPTION_TYPE.
       */
      void HandleCircularCallgraph(
         FunctionProgressIFace* progress, Function& function);
   
      //------------------------------------------------------------------------
      /** \brief After the complete list of propogating exceptions
       * has been calculated, this will filter out those exceptions
       * that will not be emitted as a result of the functions throw() 
       * specifier while emitting any warnings for such cases.
       */
      void PostProcessExceptions(Function& function);

      //------------------------------------------------------------------------
      /** \brief For internal use in calculating propogating exceptions.
       */
      void ProcessFunction(
         Function& top,
         FunctionLoc& function,
         std::list<PropogatingException>& poss_curr_catch_types);

      //------------------------------------------------------------------------
      /** \brief For internal use in calculating propogating exceptions.
       */
      void ProcessCodeBlock(
         Function& top,
         CodeBlock& block,
         FunctionLoc& function,
         std::list<PropogatingException>& poss_curr_catch_types,
         std::list<PropogatingException>& exceptions);

      //------------------------------------------------------------------------
      /** \brief For internal use in calculating propogating exceptions.
       */
      void ProcessTryBlock(
         Function& top,
         TryBlock& block,
         FunctionLoc& function,
         std::list<PropogatingException>& poss_curr_catch_types,
         std::list<PropogatingException>& exceptions);

      //------------------------------------------------------------------------
      /** \brief For internal use in ExpandCallgraph()
       */
      void UpdateFunctionAddressLists();

      //------------------------------------------------------------------------

   };
   //===========================================================================




   //===========================================================================
   // Temporary staging area for dictionaries.
   //===========================================================================
   /** \brief Returns the currently active dictionary instance that is in the
    * staging area.
    *
    * \return May return NULL if no dictionaryis currently in the staging area.
    */
   Dictionary* GetCurrentDictionary();

   //===========================================================================
   /** \brief Set the currently active dictionary.
    *
    * May set to NULL to clear the staging area.
    */
   void SetCurrentDictionary(Dictionary* current_in);

   //===========================================================================
   /** \brief Returns the currently active dictionary instance that is in the
    * staging area.
    *
    * This is used by many of the python wrappers, so before making use of the
    * python wrappers it is necessary to place a Dictionary instance in this
    * staging area.
    *
    * \return Will never return NULL, instead will throw a BugException if the
    * staging area is empty. 
    */
   Dictionary* GetCurrentDictionaryAssert();

   //===========================================================================
}

namespace std
{
   //===========================================================================
   /** \brief Print a dictionary to a std ostream.
    */
   static inline std::ostream& operator<<(std::ostream& out, 
      const EDoc::Dictionary& value)
   {
      return value.Print(out);
   }
   //===========================================================================
}

#endif // EDOC_DICTIONARY_H

---