Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 2a8f0c1669168188e34b22dccd9a154ce2c7ba79) +++ src/ResolvExpr/AlternativeFinder.cc (revision 99d45847f7626033f67b33afdf3e149972c747b0) @@ -136,5 +136,5 @@ void printAlts( const AltList &list, std::ostream &os, unsigned int indentAmt ) { - Indenter indent = { Indenter::tabsize, indentAmt }; + Indenter indent = { indentAmt }; for ( AltList::const_iterator i = list.begin(); i != list.end(); ++i ) { i->print( os, indent ); Index: src/ResolvExpr/Candidate.cpp =================================================================== --- src/ResolvExpr/Candidate.cpp (revision 99d45847f7626033f67b33afdf3e149972c747b0) +++ src/ResolvExpr/Candidate.cpp (revision 99d45847f7626033f67b33afdf3e149972c747b0) @@ -0,0 +1,55 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Candidate.cpp -- +// +// Author : Aaron B. Moss +// Created On : Wed Jun 5 14:30:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed Jun 5 14:30:00 2019 +// Update Count : 1 +// + +#include "Candidate.hpp" + +#include + +#include "AST/Print.hpp" + +namespace ResolvExpr { + +void print( std::ostream & os, const Candidate & cand, Indenter indent ) { + os << "Cost " << cand.cost << ": "; + if ( cand.expr ) { + ++indent; + ast::print( os, cand.expr, indent ); + os << std::endl << indent-1 << "(types:" << std::endl; + os << indent; + ast::print( os, cand.expr->result, indent ); + --indent; + os << std::endl << indent << ")" << std::endl; + } else { + os << "Null expression!" << std::endl; + } // if + os << indent << "Environment:"; + ast::print( os, cand.env, indent+1 ); + os << std::endl; +} + +void print( std::ostream & os, const CandidateList & cands, Indenter indent ) { + for ( const CandidateRef & cand : cands ) { + print( os, *cand, indent ); + os << std::endl; + } +} + +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/Candidate.hpp =================================================================== --- src/ResolvExpr/Candidate.hpp (revision 99d45847f7626033f67b33afdf3e149972c747b0) +++ src/ResolvExpr/Candidate.hpp (revision 99d45847f7626033f67b33afdf3e149972c747b0) @@ -0,0 +1,62 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// Candidate.hpp -- +// +// Author : Aaron B. Moss +// Created On : Wed Jun 5 14:30:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed Jun 5 14:30:00 2019 +// Update Count : 1 +// + +#pragma once + +#include +#include // for shared_ptr +#include + +#include "Cost.h" +#include "AST/Node.hpp" +#include "AST/TypeEnvironment.hpp" +#include "Common/Indenter.h" + +namespace ast { + class Expr; + + /// A list of unresolved assertions + using AssertionList = std::vector; +} + +namespace ResolvExpr { + +/// One option for resolution of an expression +struct Candidate { + ast::ptr expr; ///< Satisfying expression + Cost cost; ///< Cost of the whole expression + Cost cvtCost; ///< Cost of conversions to satisfying expression + ast::TypeEnvironment env; ///< Containing type environment + ast::OpenVarSet open; ///< Open variables for environment + ast::AssertionList need; ///< Assertions which need to be resolved +}; + +/// Shared reference to a candidate +using CandidateRef = std::shared_ptr< Candidate >; + +/// List of candidates +using CandidateList = std::vector< CandidateRef >; + +void print( std::ostream & os, const Candidate & cand, Indenter indent = {} ); + +void print( std::ostream & os, const CandidateList & cands, Indenter indent = {} ); + +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/CandidateFinder.cpp =================================================================== --- src/ResolvExpr/CandidateFinder.cpp (revision 99d45847f7626033f67b33afdf3e149972c747b0) +++ src/ResolvExpr/CandidateFinder.cpp (revision 99d45847f7626033f67b33afdf3e149972c747b0) @@ -0,0 +1,34 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// CandidateFinder.cpp -- +// +// Author : Aaron B. Moss +// Created On : Wed Jun 5 14:30:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed Jun 5 14:30:00 2019 +// Update Count : 1 +// + +#include "CandidateFinder.hpp" + +#include "AST/Expr.hpp" + +namespace ResolvExpr { + +void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) { + #warning unimplemented + (void)expr; (void)mode; + assert(false); +} + +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/CandidateFinder.hpp =================================================================== --- src/ResolvExpr/CandidateFinder.hpp (revision 99d45847f7626033f67b33afdf3e149972c747b0) +++ src/ResolvExpr/CandidateFinder.hpp (revision 99d45847f7626033f67b33afdf3e149972c747b0) @@ -0,0 +1,46 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// CandidateFinder.hpp -- +// +// Author : Aaron B. Moss +// Created On : Wed Jun 5 14:30:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed Jun 5 14:30:00 2019 +// Update Count : 1 +// + +#pragma once + +#include "Candidate.hpp" +#include "ResolvMode.h" +#include "AST/Fwd.hpp" +#include "AST/SymbolTable.hpp" +#include "AST/TypeEnvironment.hpp" + +namespace ResolvExpr { + +/// Data to perform expression resolution +struct CandidateFinder { + CandidateList candidates; ///< List of candidate resolutions + const ast::SymbolTable & symtab; ///< Symbol table to lookup candidates + const ast::TypeEnvironment & env; ///< Substitutions performed in this resolution + const ast::Type * targetType = nullptr; ///< Target type for resolution + + CandidateFinder( const ast::SymbolTable & symtab, const ast::TypeEnvironment & env ) + : candidates(), symtab( symtab ), env( env ) {} + + /// Fill candidates with feasible resolutions for `expr` + void find( const ast::Expr * expr, ResolvMode mode = {} ); +}; + +} // namespace ResolvExpr + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/ResolvExpr/ResolveAssertions.cc =================================================================== --- src/ResolvExpr/ResolveAssertions.cc (revision 2a8f0c1669168188e34b22dccd9a154ce2c7ba79) +++ src/ResolvExpr/ResolveAssertions.cc (revision 99d45847f7626033f67b33afdf3e149972c747b0) @@ -365,5 +365,5 @@ // fail early if any assertion is not resolvable if ( ! resolveAssertion( assn, resn ) ) { - Indenter tabs{ Indenter::tabsize, 3 }; + Indenter tabs{ 3 }; std::ostringstream ss; ss << tabs << "Unsatisfiable alternative:\n"; @@ -391,5 +391,5 @@ // fail early if no mutually-compatible assertion satisfaction if ( compatible.empty() ) { - Indenter tabs{ Indenter::tabsize, 3 }; + Indenter tabs{ 3 }; std::ostringstream ss; ss << tabs << "Unsatisfiable alternative:\n"; Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision 2a8f0c1669168188e34b22dccd9a154ce2c7ba79) +++ src/ResolvExpr/Resolver.cc (revision 99d45847f7626033f67b33afdf3e149972c747b0) @@ -21,4 +21,6 @@ #include "Alternative.h" // for Alternative, AltList #include "AlternativeFinder.h" // for AlternativeFinder, resolveIn... +#include "Candidate.hpp" +#include "CandidateFinder.hpp" #include "CurrentObject.h" // for CurrentObject #include "RenameVars.h" // for RenameVars, global_renamer @@ -30,4 +32,5 @@ #include "AST/Init.hpp" #include "AST/Pass.hpp" +#include "AST/Print.hpp" #include "AST/SymbolTable.hpp" #include "Common/PassVisitor.h" // for PassVisitor @@ -115,5 +118,5 @@ namespace { - struct DeleteFinder : public WithShortCircuiting { + struct DeleteFinder_old : public WithShortCircuiting { DeletedExpr * delExpr = nullptr; void previsit( DeletedExpr * expr ) { @@ -129,5 +132,5 @@ DeletedExpr * findDeletedExpr( Expression * expr ) { - PassVisitor finder; + PassVisitor finder; expr->accept( finder ); return finder.pass.delExpr; @@ -135,5 +138,5 @@ namespace { - struct StripCasts { + struct StripCasts_old { Expression * postmutate( CastExpr * castExpr ) { if ( castExpr->isGenerated && ResolvExpr::typesCompatible( castExpr->arg->result, castExpr->result, SymTab::Indexer() ) ) { @@ -148,5 +151,5 @@ static void strip( Expression *& expr ) { - PassVisitor stripper; + PassVisitor stripper; expr = expr->acceptMutator( stripper ); } @@ -156,5 +159,5 @@ expr->env = oldenv ? oldenv->clone() : new TypeSubstitution; env.makeSubstitution( *expr->env ); - StripCasts::strip( expr ); // remove unnecessary casts that may be buried in an expression + StripCasts_old::strip( expr ); // remove unnecessary casts that may be buried in an expression } @@ -939,4 +942,180 @@ /////////////////////////////////////////////////////////////////////////// + namespace { + /// Finds deleted expressions in an expression tree + struct DeleteFinder_new final : public ast::WithShortCircuiting { + const ast::DeletedExpr * delExpr = nullptr; + + void previsit( const ast::DeletedExpr * expr ) { + if ( delExpr ) { visit_children = false; } + else { delExpr = expr; } + } + + void previsit( const ast::Expr * ) { + if ( delExpr ) { visit_children = false; } + } + }; + + /// Check if this expression is or includes a deleted expression + const ast::DeletedExpr * findDeletedExpr( const ast::Expr * expr ) { + ast::Pass finder; + expr->accept( finder ); + return finder.pass.delExpr; + } + + /// Calls the CandidateFinder and finds the single best candidate + CandidateRef findUnfinishedKindExpression( + const ast::Expr * untyped, const ast::SymbolTable & symtab, const std::string & kind, + std::function pred, ResolvMode mode = {} + ) { + if ( ! untyped ) return nullptr; + + // xxx - this isn't thread-safe, but should work until we parallelize the resolver + static unsigned recursion_level = 0; + + ++recursion_level; + ast::TypeEnvironment env; + CandidateFinder finder{ symtab, env }; + finder.find( untyped, recursion_level == 1 ? mode.atTopLevel() : mode ); + --recursion_level; + + // produce a filtered list of candidates + CandidateList candidates; + for ( auto & cand : finder.candidates ) { + if ( pred( *cand ) ) { candidates.emplace_back( cand ); } + } + + // produce invalid error if no candidates + if ( candidates.empty() ) { + SemanticError( untyped, + toString( "No reasonable alternatives for ", kind, (kind != "" ? " " : ""), + "expression: ") ); + } + + // search for cheapest candidate + CandidateList winners; + bool seen_undeleted = false; + for ( CandidateRef & cand : candidates ) { + int c = winners.empty() ? -1 : cand->cost.compare( winners.front()->cost ); + + if ( c > 0 ) continue; // skip more expensive than winner + + if ( c < 0 ) { + // reset on new cheapest + seen_undeleted = ! findDeletedExpr( cand->expr ); + winners.clear(); + } else /* if ( c == 0 ) */ { + if ( findDeletedExpr( cand->expr ) ) { + // skip deleted expression if already seen one equivalent-cost not + if ( seen_undeleted ) continue; + } else if ( ! seen_undeleted ) { + // replace list of equivalent-cost deleted expressions with one non-deleted + winners.clear(); + seen_undeleted = true; + } + } + + winners.emplace_back( std::move( cand ) ); + } + + // promote candidate.cvtCost to .cost + for ( CandidateRef & cand : winners ) { + cand->cost = cand->cvtCost; + } + + // produce ambiguous errors, if applicable + if ( winners.size() != 1 ) { + std::ostringstream stream; + stream << "Cannot choose between " << winners.size() << " alternatives for " + << kind << (kind != "" ? " " : "") << "expression\n"; + ast::print( stream, untyped ); + stream << " Alternatives are:\n"; + print( stream, winners, 1 ); + SemanticError( untyped->location, stream.str() ); + } + + // single selected choice + CandidateRef & choice = winners.front(); + + // fail on only expression deleted + if ( ! seen_undeleted ) { + SemanticError( untyped->location, choice->expr.get(), "Unique best alternative " + "includes deleted identifier in " ); + } + + return std::move( choice ); + } + + /// Strips extraneous casts out of an expression + struct StripCasts_new final { + const ast::Expr * postmutate( const ast::CastExpr * castExpr ) { + if ( + castExpr->isGenerated + && typesCompatible( castExpr->arg->result, castExpr->result ) + ) { + // generated cast is the same type as its argument, remove it after keeping env + ast::ptr arg = castExpr->arg; + arg.get_and_mutate()->env = castExpr->env; + return arg; + } + return castExpr; + } + + static void strip( ast::ptr< ast::Expr > & expr ) { + ast::Pass< StripCasts_new > stripper; + expr = expr->accept( stripper ); + } + }; + + /// Establish post-resolver invariants for expressions + void finishExpr( + ast::ptr< ast::Expr > & expr, const ast::TypeEnvironment & env, + const ast::TypeSubstitution * oldenv = nullptr + ) { + // set up new type substitution for expression + ast::ptr< ast::TypeSubstitution > newenv = + oldenv ? oldenv : new ast::TypeSubstitution{}; + env.writeToSubstitution( *newenv.get_and_mutate() ); + expr.get_and_mutate()->env = std::move( newenv ); + // remove unncecessary casts + StripCasts_new::strip( expr ); + } + + /// resolve `untyped` to the expression whose candidate satisfies `pred` with the + /// lowest cost, returning the resolved version + ast::ptr< ast::Expr > findKindExpression( + const ast::Expr * untyped, const ast::SymbolTable & symtab, const std::string & kind, + std::function pred, ResolvMode mode = {} + ) { + if ( ! untyped ) return {}; + CandidateRef choice = + findUnfinishedKindExpression( untyped, symtab, kind, pred, mode ); + finishExpr( choice->expr, choice->env, untyped->env ); + return std::move( choice->expr ); + } + + /// Predicate for "Candidate has integral type" + bool hasIntegralType( const Candidate & i ) { + const ast::Type * type = i.expr->result; + + if ( auto bt = dynamic_cast< const ast::BasicType * >( type ) ) { + return bt->isInteger(); + } else if ( + dynamic_cast< const ast::EnumInstType * >( type ) + || dynamic_cast< const ast::ZeroType * >( type ) + || dynamic_cast< const ast::OneType * >( type ) + ) { + return true; + } else return false; + } + + /// Resolve `untyped` as an integral expression, returning the resolved version + ast::ptr< ast::Expr > findIntegralExpression( + const ast::Expr * untyped, const ast::SymbolTable & symtab + ) { + return findKindExpression( untyped, symtab, "condition", hasIntegralType ); + } + } + class Resolver_new final : public ast::WithSymbolTable, public ast::WithGuards, @@ -946,5 +1125,5 @@ ast::ptr< ast::Type > functionReturn = nullptr; // ast::CurrentObject currentObject = nullptr; - // bool inEnumDecl = false; + bool inEnumDecl = false; public: @@ -952,30 +1131,30 @@ Resolver_new( const ast::SymbolTable & syms ) { symtab = syms; } - void previsit( const ast::FunctionDecl * functionDecl ); - const ast::FunctionDecl * postvisit( const ast::FunctionDecl * functionDecl ); - void previsit( const ast::ObjectDecl * objectDecl ); - void previsit( const ast::EnumDecl * enumDecl ); - void previsit( const ast::StaticAssertDecl * assertDecl ); - - void previsit( const ast::ArrayType * at ); - void previsit( const ast::PointerType * pt ); - - void previsit( const ast::ExprStmt * exprStmt ); - void previsit( const ast::AsmExpr * asmExpr ); - void previsit( const ast::AsmStmt * asmStmt ); - void previsit( const ast::IfStmt * ifStmt ); - void previsit( const ast::WhileStmt * whileStmt ); - void previsit( const ast::ForStmt * forStmt ); - void previsit( const ast::SwitchStmt * switchStmt ); - void previsit( const ast::CaseStmt * caseStmt ); - void previsit( const ast::BranchStmt * branchStmt ); - void previsit( const ast::ReturnStmt * returnStmt ); - void previsit( const ast::ThrowStmt * throwStmt ); - void previsit( const ast::CatchStmt * catchStmt ); - void previsit( const ast::WaitForStmt * stmt ); - - void previsit( const ast::SingleInit * singleInit ); - void previsit( const ast::ListInit * listInit ); - void previsit( const ast::ConstructorInit * ctorInit ); + void previsit( const ast::FunctionDecl * ); + const ast::FunctionDecl * postvisit( const ast::FunctionDecl * ); + void previsit( const ast::ObjectDecl * ); + void previsit( const ast::EnumDecl * ); + const ast::StaticAssertDecl * previsit( const ast::StaticAssertDecl * ); + + void previsit( const ast::ArrayType * ); + void previsit( const ast::PointerType * ); + + void previsit( const ast::ExprStmt * ); + void previsit( const ast::AsmExpr * ); + void previsit( const ast::AsmStmt * ); + void previsit( const ast::IfStmt * ); + void previsit( const ast::WhileStmt * ); + void previsit( const ast::ForStmt * ); + void previsit( const ast::SwitchStmt * ); + void previsit( const ast::CaseStmt * ); + void previsit( const ast::BranchStmt * ); + void previsit( const ast::ReturnStmt * ); + void previsit( const ast::ThrowStmt * ); + void previsit( const ast::CatchStmt * ); + void previsit( const ast::WaitForStmt * ); + + void previsit( const ast::SingleInit * ); + void previsit( const ast::ListInit * ); + void previsit( const ast::ConstructorInit * ); }; @@ -1018,14 +1197,19 @@ } - void Resolver_new::previsit( const ast::EnumDecl * enumDecl ) { - #warning unimplemented; Resolver port in progress - (void)enumDecl; - assert(false); - } - - void Resolver_new::previsit( const ast::StaticAssertDecl * assertDecl ) { - #warning unimplemented; Resolver port in progress - (void)assertDecl; - assert(false); + void Resolver_new::previsit( const ast::EnumDecl * ) { + // in case we decide to allow nested enums + GuardValue( inEnumDecl ); + inEnumDecl = false; + } + + const ast::StaticAssertDecl * Resolver_new::previsit( + const ast::StaticAssertDecl * assertDecl + ) { + ast::ptr< ast::Expr > cond = findIntegralExpression( assertDecl->cond, symtab ); + if ( cond == assertDecl->cond ) return assertDecl; + + ast::StaticAssertDecl * ret = mutate( assertDecl ); + ret->cond = cond; + return ret; } Index: src/ResolvExpr/module.mk =================================================================== --- src/ResolvExpr/module.mk (revision 2a8f0c1669168188e34b22dccd9a154ce2c7ba79) +++ src/ResolvExpr/module.mk (revision 99d45847f7626033f67b33afdf3e149972c747b0) @@ -19,4 +19,6 @@ ResolvExpr/Alternative.cc \ ResolvExpr/AlternativeFinder.cc \ + ResolvExpr/Candidate.cpp \ + ResolvExpr/CandidateFinder.cpp \ ResolvExpr/CastCost.cc \ ResolvExpr/CommonType.cc \ Index: src/ResolvExpr/typeops.h =================================================================== --- src/ResolvExpr/typeops.h (revision 2a8f0c1669168188e34b22dccd9a154ce2c7ba79) +++ src/ResolvExpr/typeops.h (revision 99d45847f7626033f67b33afdf3e149972c747b0) @@ -103,5 +103,5 @@ bool typesCompatible( - const ast::Type *, const ast::Type *, const ast::SymbolTable &, + const ast::Type *, const ast::Type *, const ast::SymbolTable & symtab = {}, const ast::TypeEnvironment & env = {} );