// $Id: depend.cpp,v 1.6 1999/03/10 19:59:21 shields Exp $
copyright notice

#include "config.h"
#include <time.h>
#include "control.h"
#include "ast.h"
#include "semantic.h"

//
// Note that the types are ordered based on on the subtype relationship. We reverse
// the order here because the desired order for processing is the supertype relationship.
//
inline void TypeCycleChecker::ReverseTypeList()
{
    int head,
        tail;
    for (head = 0, tail = type_list.Length() - 1; head < tail; head++, tail--)
    {
        TypeSymbol *temp = type_list[head];
        type_list[head] = type_list[tail];
        type_list[tail] = temp;
    }

    return;
}


void TypeCycleChecker::PartialOrder(Tuple<Semantic *> &semantic, int start)
{
    type_list.Reset();

    //
    // assert that the "index" of all types that should be checked is initially set to OMEGA
    //
    for (int i = start; i < semantic.Length(); i++)
    {
        Semantic *sem = semantic[i];

        for (int k = 0; k < sem -> compilation_unit -> NumTypeDeclarations(); k++)
        {
            AstClassDeclaration *class_declaration = sem -> compilation_unit -> TypeDeclaration(k) -> ClassDeclarationCast();
            AstInterfaceDeclaration *interface_declaration = sem -> compilation_unit -> TypeDeclaration(k) -> InterfaceDeclarationCast();
            if (class_declaration || interface_declaration)
            {
                SemanticEnvironment *env = (class_declaration ? class_declaration -> semantic_environment
                                                              : interface_declaration -> semantic_environment);
                if (env) // type was successfully compiled thus far?
                {
                    TypeSymbol *type = env -> Type();
                    if (type -> index == OMEGA)
                       ProcessSubtypes(type);
                }
            }
        }
    }

    ReverseTypeList();

    return;
}


void TypeCycleChecker::PartialOrder(SymbolSet &types)
{
    //
    // assert that the "index" of all types that should be checked is initially set to OMEGA
    //
    for (TypeSymbol *type = (TypeSymbol *) types.FirstElement(); type; type = (TypeSymbol *) types.NextElement())
    {
        if (type -> index == OMEGA)
            ProcessSubtypes(type);
    }

    ReverseTypeList();

    return;
}


void TypeCycleChecker::ProcessSubtypes(TypeSymbol *type)
{
    stack.Push(type);
    int indx = stack.Size();
    type -> index = indx;

    type -> subtypes_closure = new SymbolSet;
    type -> subtypes_closure -> Union(*(type -> subtypes));
    for (TypeSymbol *subtype = (TypeSymbol *) type -> subtypes -> FirstElement();
                     subtype;
                     subtype = (TypeSymbol *) type -> subtypes -> NextElement())
    {
        if (subtype -> index == OMEGA)
             ProcessSubtypes(subtype);
        type -> index = Min(type -> index, subtype -> index);
        type -> subtypes_closure -> Union(*(subtype -> subtypes_closure));
    }

    if (type -> index == indx)
    {
        TypeSymbol *scc_subtype;
        do
        {
            scc_subtype = stack.Top();
            scc_subtype -> index = INFINITY;
            *(scc_subtype -> subtypes_closure) = *(type -> subtypes_closure);
            type_list.Next() = scc_subtype;
            stack.Pop();
        } while (scc_subtype != type);
    }

    return;
}


ConstructorCycleChecker::ConstructorCycleChecker(AstClassBody *class_body)
{
    for (int k = 0; k < class_body -> NumConstructors(); k++)
    {
        AstConstructorDeclaration *constructor_declaration = class_body -> Constructor(k);
        if (constructor_declaration -> index == OMEGA)
            CheckConstructorCycles(constructor_declaration);
    }

    return;
}


void ConstructorCycleChecker::CheckConstructorCycles(AstConstructorDeclaration *constructor_declaration)
{
    stack.Push(constructor_declaration);
    int indx = stack.Size();
    constructor_declaration -> index = indx;

    AstConstructorDeclaration *called_constructor_declaration = NULL;

    AstConstructorBlock *constructor_block = constructor_declaration -> constructor_body;
    if (constructor_block -> explicit_constructor_invocation_opt)
    {
        AstThisCall *this_call = constructor_block -> explicit_constructor_invocation_opt -> ThisCallCast();
        MethodSymbol *called_constructor = (MethodSymbol *) (this_call ? this_call -> symbol : NULL);

        if (called_constructor)
        {
            called_constructor_declaration = (AstConstructorDeclaration *) called_constructor -> method_or_constructor_declaration;

            if (called_constructor_declaration -> index == OMEGA)
                CheckConstructorCycles(called_constructor_declaration);
            constructor_declaration -> index = Min(constructor_declaration -> index, called_constructor_declaration -> index);
        }
    }

    if (constructor_declaration -> index == indx)
    {
        //
        // If the constructor_declaration is alone in its strongly connected component (SCC),
        // and it does not form a trivial cycle with itsself, pop it, mark it and return;
        //
        if (constructor_declaration == stack.Top() && constructor_declaration != called_constructor_declaration)
        {
            stack.Pop();
            constructor_declaration -> index = INFINITY;
        }
        //
        // Otherwise, all elements in the stack up to (and including) constructor_declaration form an SCC.
        // Pop them off the stack, in turn, mark them and issue the appropriate error message.
        //
        else
        {
            do 
            {
                called_constructor_declaration = stack.Top();
                stack.Pop();
                called_constructor_declaration -> index = INFINITY;

                constructor_block = (AstConstructorBlock *) called_constructor_declaration -> constructor_body;
                AstMethodDeclarator *constructor_declarator = called_constructor_declaration -> constructor_declarator;

                Semantic *sem = called_constructor_declaration -> constructor_symbol
                                                               -> containing_type -> semantic_environment -> sem;
                sem -> ReportSemError(SemanticError::CIRCULAR_THIS_CALL,
                                       constructor_block -> explicit_constructor_invocation_opt -> LeftToken(),
                                       constructor_block -> explicit_constructor_invocation_opt -> RightToken(),
                                       sem -> lex_stream -> Name(constructor_declarator -> identifier_token));
            } while (called_constructor_declaration != constructor_declaration);
        }
    }

    return;
}


//
// assert that the "index" of all types that should be checked is initially set to OMEGA
//
void TypeDependenceChecker::PartialOrder()
{
    for (FileSymbol *file_symbol = (FileSymbol *) file_set.FirstElement();
                     file_symbol;
                     file_symbol = (FileSymbol *) file_set.NextElement())
    {
        for (int j = 0; j < file_symbol -> types.Length(); j++)
        {
            TypeSymbol *type = file_symbol -> types[j];
            if (type -> incremental_index == OMEGA)
                ProcessType(type);
        }
    }

    for (int k = 0; k < type_trash_bin.Length(); k++)
    {
        TypeSymbol *type = type_trash_bin[k];
        if (type -> incremental_index == OMEGA)
            ProcessType(type);
    }

    return;
}


void TypeDependenceChecker::ProcessType(TypeSymbol *type)
{
    stack.Push(type);
    int indx = stack.Size();
    type -> incremental_index = indx;

    type -> dependents -> RemoveElement(type); // if dependents is reflexive make it non-reflexive - saves time !!!
    type -> dependents_closure = new SymbolSet;
    type -> dependents_closure -> AddElement(type); // compute reflexive transitive closure
    for (TypeSymbol *dependent = (TypeSymbol *) type -> dependents -> FirstElement();
                     dependent;
                     dependent = (TypeSymbol *) type -> dependents -> NextElement())
    {
        if (dependent -> incremental_index == OMEGA)
             ProcessType(dependent);
        type -> incremental_index = Min(type -> incremental_index, dependent -> incremental_index);
        type -> dependents_closure -> Union(*(dependent -> dependents_closure));
    }

    if (type -> incremental_index == indx)
    {
        TypeSymbol *scc_dependent;
        do
        {
            scc_dependent = stack.Top();
            scc_dependent -> incremental_index = INFINITY;
            *(scc_dependent -> dependents_closure) = *(type -> dependents_closure);
            type_list.Next() = scc_dependent;
            stack.Pop();
        } while (scc_dependent != type);
    }

    return;
}


void TypeDependenceChecker::OutputMake(FILE *outfile, char *output_name, Tuple<FileSymbol *> &file_list)
{
    if (outfile)
    {
        for (int i = 0; i < file_list.Length(); i++)
        {
            FileSymbol *file_symbol = file_list[i];
            char *name = file_symbol -> FileName();
            int length = file_symbol -> FileNameLength() - (file_symbol -> IsJava() ? FileSymbol::java_suffix_length
                                                                                    : FileSymbol::class_suffix_length);

            char *class_name = new char[length + FileSymbol::class_suffix_length + 1],
                 *java_name = new char[length + FileSymbol::java_suffix_length + 1];

            strncpy(class_name, name, length);
            strcpy(&class_name[length], FileSymbol::class_suffix);
            strncpy(java_name, name, length);
            strcpy(&java_name[length], FileSymbol::java_suffix);

            struct stat status;

            if ((::SystemStat(java_name,  &status) == 0) && (status.st_mode  & STAT_S_IFREG)) {
                fprintf(outfile, "%s: ", output_name);
#ifdef EBCDIC
                char * charp = java_name;
                charp = java_name;
                while (*charp) fprintf(outfile, "%c", Code::ToEBCDIC(*charp++));
#else
                fprintf(outfile, "%s", java_name);
#endif
                fprintf(outfile, "\n");
                
            }
            
            if (i > 0) // Not the first file in the list
            {
                if ((::SystemStat(class_name, &status) == 0) && (status.st_mode & STAT_S_IFREG)) {
                fprintf(outfile, "%s: ", output_name);
#ifdef EBCDIC
                char * charp = class_name;
                while (*charp) fprintf(outfile, "%c", Code::ToEBCDIC(*charp++));
#else
                fprintf(outfile, "%s", class_name);
#endif
                fprintf(outfile, "\n");
                }
            }

            delete [] class_name;
            delete [] java_name;
        }
    }

    return;
}


void TypeDependenceChecker::OutputMake(FILE *outfile, FileSymbol *file_symbol)
{
    //
    //
    //
    char *name = file_symbol -> FileName();
    int length = file_symbol -> FileNameLength() - (file_symbol -> IsJava() ? FileSymbol::java_suffix_length
                                                                            : FileSymbol::class_suffix_length);

    char *output_name = new char[length + FileSymbol::class_suffix_length + 1],
         *u_name = new char[length + strlen(StringConstant::U8S__DO_u) + 1];

    strncpy(output_name, name, length);
    strncpy(u_name, name, length);
    strcpy(&output_name[length], FileSymbol::class_suffix);
    strcpy(&u_name[length], StringConstant::U8S__DO_u);

    //
    //
    //
    SymbolSet file_set;
    for (int i = 0; i < file_symbol -> types.Length(); i++)
    {
        TypeSymbol *type = file_symbol -> types[i];
        for (TypeSymbol *parent = (TypeSymbol *) type -> parents_closure -> FirstElement();
                         parent;
                         parent = (TypeSymbol *) type -> parents_closure -> NextElement())
        {
            FileSymbol *symbol = parent -> file_symbol;
            if (symbol && (! symbol -> IsZip()))
                file_set.AddElement(symbol);
        }
    }
    file_set.RemoveElement(file_symbol);

    //
    //
    //
    Tuple<FileSymbol *> file_list(file_set.Size());
    file_list.Next() = file_symbol;
    for (FileSymbol *symbol = (FileSymbol *) file_set.FirstElement(); symbol; symbol = (FileSymbol *) file_set.NextElement())
        file_list.Next() = symbol;

    if (outfile) // A single output makefile was specified
        OutputMake(outfile, output_name, file_list);
    else
    {
        outfile = ::SystemFopen(u_name, "w");
        if (outfile == NULL)
            cout << "*** Cannot open file " << u_name << "\n";
        else
        {
            OutputMake(outfile, output_name, file_list);
            fclose(outfile);
        }
    }

    delete [] output_name;
    delete [] u_name;

    return;
}


void TypeDependenceChecker::OutputDependences()
{
    SymbolSet new_file_set;

    for (int i = 0; i < type_list.Length(); i++)
    {
        TypeSymbol *type = type_list[i];
        type -> parents_closure = new SymbolSet;

        FileSymbol *file_symbol = type -> file_symbol;
        if (file_symbol && (! file_symbol -> IsZip()))
            new_file_set.AddElement(file_symbol);
    }

    for (int l = 0; l < type_list.Length(); l++)
    {
        TypeSymbol *parent = type_list[l];

        for (TypeSymbol *dependent = (TypeSymbol *) parent -> dependents_closure -> FirstElement();
                         dependent;
                         dependent = (TypeSymbol *) parent -> dependents_closure -> NextElement())
                dependent -> parents_closure -> AddElement(parent);
    }

    FILE *outfile = NULL;
    if (control -> option.makefile_name)
    {
        outfile = ::SystemFopen(control -> option.makefile_name, "w");
        if (outfile == NULL)
            cout << "*** Cannot open file " << control -> option.makefile_name << "\n";
    }

    for (FileSymbol *symbol = (FileSymbol *) new_file_set.FirstElement(); symbol; symbol = (FileSymbol *) new_file_set.NextElement())
        OutputMake(outfile, symbol);

    for (int n = 0; n < type_list.Length(); n++)
    {
        TypeSymbol *type = type_list[n];
        delete type -> parents_closure;
        type -> parents_closure = NULL;
    }

    return;
}


void TopologicalSort::Process(TypeSymbol *type)
{
    pending -> AddElement(type);

    for (TypeSymbol *super_type = (TypeSymbol *) type -> supertypes_closure -> FirstElement();
                     super_type;
                     super_type = (TypeSymbol *) type -> supertypes_closure -> NextElement())
    {
        if (type_collection.IsElement(super_type))
        {
            if (! pending -> IsElement(super_type))
                Process(super_type);
        }
    }

    type_list.Next() = type;

    return;
}


void TopologicalSort::Sort()
{
    type_list.Reset();

    for (TypeSymbol *type = (TypeSymbol *) type_collection.FirstElement(); type; type = (TypeSymbol *) type_collection.NextElement())
    {
        if (! pending -> IsElement(type))
            Process(type);
    }

    pending -> SetEmpty();

    return;
}


TopologicalSort::TopologicalSort(SymbolSet &type_collection_, Tuple<TypeSymbol *> &type_list_) : type_collection(type_collection_),
                                                                                                 type_list(type_list_)
{
    pending = new SymbolSet(type_collection.Size());

    return;
}


TopologicalSort::~TopologicalSort()
{
    delete pending;
}