Changeset 2773ab8
- Timestamp:
- Jun 10, 2019, 5:20:07 PM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 5485e101
- Parents:
- 6949c45
- Location:
- src/ResolvExpr
- Files:
-
- 5 edited
-
CandidateFinder.cpp (modified) (1 diff)
-
CandidateFinder.hpp (modified) (1 diff)
-
Resolver.cc (modified) (9 diffs)
-
Unify.cc (modified) (1 diff)
-
Unify.h (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/CandidateFinder.cpp
r6949c45 r2773ab8 26 26 } 27 27 28 std::vector< CandidateFinder > CandidateFinder::findSubExprs( 29 const std::vector< ast::ptr< ast::Expr > > & xs 30 ) { 31 std::vector< CandidateFinder > out; 32 33 #warning unimplemented 34 (void)xs; 35 assert(false); 36 37 return out; 38 } 39 28 40 } // namespace ResolvExpr 29 41 -
src/ResolvExpr/CandidateFinder.hpp
r6949c45 r2773ab8 36 36 /// Fill candidates with feasible resolutions for `expr` 37 37 void find( const ast::Expr * expr, ResolvMode mode = {} ); 38 39 /// Runs new candidate finder on each element in xs, returning the list of finders 40 std::vector< CandidateFinder > findSubExprs( const std::vector< ast::ptr< ast::Expr > > & xs ); 41 42 using value_type = CandidateList::value_type; 43 using iterator = CandidateList::iterator; 44 using const_iterator = CandidateList::const_iterator; 45 46 iterator begin() { return candidates.begin(); } 47 const_iterator begin() const { return candidates.begin(); } 48 49 iterator end() { return candidates.end(); } 50 const_iterator end() const { return candidates.end(); } 38 51 }; 39 52 -
src/ResolvExpr/Resolver.cc
r6949c45 r2773ab8 35 35 #include "AST/Print.hpp" 36 36 #include "AST/SymbolTable.hpp" 37 #include "AST/Type.hpp" 37 38 #include "Common/PassVisitor.h" // for PassVisitor 38 39 #include "Common/SemanticError.h" // for SemanticError … … 1146 1147 } 1147 1148 1149 /// Resolve `untyped` to the single expression whose candidate is the best match 1150 ast::ptr< ast::Expr > findSingleExpression( 1151 const ast::Expr * untyped, const ast::SymbolTable & symtab 1152 ) { 1153 return findKindExpression( untyped, symtab ); 1154 } 1155 1148 1156 /// Resolve `untyped` to the single expression whose candidate is the best match for the 1149 1157 /// given type. … … 1152 1160 ) { 1153 1161 assert( untyped && type ); 1154 const ast::Expr *castExpr = new ast::CastExpr{ untyped->location, untyped, type };1155 ast::ptr< ast::Expr > newExpr = find KindExpression( castExpr, symtab );1162 ast::ptr< ast::Expr > castExpr = new ast::CastExpr{ untyped->location, untyped, type }; 1163 ast::ptr< ast::Expr > newExpr = findSingleExpression( castExpr, symtab ); 1156 1164 removeExtraneousCast( newExpr, symtab ); 1157 1165 return newExpr; … … 1189 1197 return false; 1190 1198 } 1199 1200 /// Advance a type itertor to the next mutex parameter 1201 template<typename Iter> 1202 inline bool nextMutex( Iter & it, const Iter & end ) { 1203 while ( it != end && ! (*it)->get_type()->is_mutex() ) { ++it; } 1204 return it != end; 1205 } 1191 1206 } 1192 1207 … … 1213 1228 void previsit( const ast::PointerType * ); 1214 1229 1215 const ast::ExprStmt * previsit( const ast::ExprStmt * );1216 const ast::AsmExpr * previsit( const ast::AsmExpr * );1217 const ast::AsmStmt * previsit( const ast::AsmStmt * );1218 const ast::IfStmt * previsit( const ast::IfStmt * );1219 const ast::WhileStmt * previsit( const ast::WhileStmt * );1220 const ast::ForStmt * previsit( const ast::ForStmt * );1221 const ast::SwitchStmt * previsit( const ast::SwitchStmt * );1222 const ast::CaseStmt * previsit( const ast::CaseStmt * );1223 const ast::BranchStmt * previsit( const ast::BranchStmt * );1224 const ast::ReturnStmt * previsit( const ast::ReturnStmt * );1225 const ast::ThrowStmt * previsit( const ast::ThrowStmt * );1226 const ast::CatchStmt * previsit( const ast::CatchStmt * );1227 voidprevisit( const ast::WaitForStmt * );1230 const ast::ExprStmt * previsit( const ast::ExprStmt * ); 1231 const ast::AsmExpr * previsit( const ast::AsmExpr * ); 1232 const ast::AsmStmt * previsit( const ast::AsmStmt * ); 1233 const ast::IfStmt * previsit( const ast::IfStmt * ); 1234 const ast::WhileStmt * previsit( const ast::WhileStmt * ); 1235 const ast::ForStmt * previsit( const ast::ForStmt * ); 1236 const ast::SwitchStmt * previsit( const ast::SwitchStmt * ); 1237 const ast::CaseStmt * previsit( const ast::CaseStmt * ); 1238 const ast::BranchStmt * previsit( const ast::BranchStmt * ); 1239 const ast::ReturnStmt * previsit( const ast::ReturnStmt * ); 1240 const ast::ThrowStmt * previsit( const ast::ThrowStmt * ); 1241 const ast::CatchStmt * previsit( const ast::CatchStmt * ); 1242 const ast::WaitForStmt * previsit( const ast::WaitForStmt * ); 1228 1243 1229 1244 const ast::SingleInit * previsit( const ast::SingleInit * ); … … 1381 1396 "expression." ); 1382 1397 1383 const ast::Expr *untyped =1398 ast::ptr< ast::Expr > untyped = 1384 1399 new ast::CastExpr{ caseStmt->location, caseStmt->cond, initAlts.front().type }; 1385 ast::ptr< ast::Expr > newExpr = find KindExpression( untyped, symtab );1400 ast::ptr< ast::Expr > newExpr = findSingleExpression( untyped, symtab ); 1386 1401 1387 1402 // case condition cannot have a cast in C, so it must be removed here, regardless of … … 1401 1416 if ( branchStmt->kind == ast::BranchStmt::Goto && branchStmt->computedTarget ) { 1402 1417 // computed goto argument is void* 1418 ast::ptr< ast::Type > target = new ast::PointerType{ new ast::VoidType{} }; 1403 1419 branchStmt = ast::mutate_field( 1404 1420 branchStmt, &ast::BranchStmt::computedTarget, 1405 findSingleExpression( 1406 branchStmt->computedTarget, new ast::PointerType{ new ast::VoidType{} }, 1407 symtab ) ); 1421 findSingleExpression( branchStmt->computedTarget, target, symtab ) ); 1408 1422 } 1409 1423 return branchStmt; … … 1445 1459 } 1446 1460 1447 void Resolver_new::previsit( const ast::WaitForStmt * stmt ) { 1448 #warning unimplemented; Resolver port in progress 1449 (void)stmt; 1450 assert(false); 1461 const ast::WaitForStmt * Resolver_new::previsit( const ast::WaitForStmt * stmt ) { 1462 visit_children = false; 1463 1464 // Resolve all clauses first 1465 for ( unsigned i = 0; i < stmt->clauses.size(); ++i ) { 1466 const ast::WaitForStmt::Clause & clause = stmt->clauses[i]; 1467 1468 ast::TypeEnvironment env; 1469 CandidateFinder funcFinder{ symtab, env }; 1470 1471 // Find all candidates for a function in canonical form 1472 funcFinder.find( clause.target.func, ResolvMode::withAdjustment() ); 1473 1474 if ( funcFinder.candidates.empty() ) { 1475 stringstream ss; 1476 ss << "Use of undeclared indentifier '"; 1477 ss << clause.target.func.strict_as< ast::NameExpr >()->name; 1478 ss << "' in call to waitfor"; 1479 SemanticError( stmt->location, ss.str() ); 1480 } 1481 1482 if ( clause.target.args.empty() ) { 1483 SemanticError( stmt->location, 1484 "Waitfor clause must have at least one mutex parameter"); 1485 } 1486 1487 // Find all alternatives for all arguments in canonical form 1488 std::vector< CandidateFinder > argFinders = 1489 funcFinder.findSubExprs( clause.target.args ); 1490 1491 // List all combinations of arguments 1492 std::vector< CandidateList > possibilities; 1493 combos( argFinders.begin(), argFinders.end(), back_inserter( possibilities ) ); 1494 1495 // For every possible function: 1496 // * try matching the arguments to the parameters, not the other way around because 1497 // more arguments than parameters 1498 CandidateList funcCandidates; 1499 std::vector< CandidateList > argsCandidates; 1500 SemanticErrorException errors; 1501 for ( CandidateRef & func : funcFinder.candidates ) { 1502 try { 1503 auto pointerType = dynamic_cast< const ast::PointerType * >( 1504 func->expr->result->stripReferences() ); 1505 if ( ! pointerType ) { 1506 SemanticError( stmt->location, func->expr->result.get(), 1507 "candidate not viable: not a pointer type\n" ); 1508 } 1509 1510 auto funcType = pointerType->base.as< ast::FunctionType >(); 1511 if ( ! funcType ) { 1512 SemanticError( stmt->location, func->expr->result.get(), 1513 "candidate not viable: not a function type\n" ); 1514 } 1515 1516 { 1517 auto param = funcType->params.begin(); 1518 auto paramEnd = funcType->params.end(); 1519 1520 if( ! nextMutex( param, paramEnd ) ) { 1521 SemanticError( stmt->location, funcType, 1522 "candidate function not viable: no mutex parameters\n"); 1523 } 1524 } 1525 1526 CandidateRef func2{ new Candidate{ *func } }; 1527 // strip reference from function 1528 func2->expr = referenceToRvalueConversion( func->expr, func2->cost ); 1529 1530 // Each argument must be matched with a parameter of the current candidate 1531 for ( auto & argsList : possibilities ) { 1532 try { 1533 // Declare data structures needed for resolution 1534 ast::OpenVarSet open; 1535 ast::AssertionSet need, have; 1536 ast::TypeEnvironment resultEnv{ func->env }; 1537 // Add all type variables as open so that those not used in the 1538 // parameter list are still considered open 1539 resultEnv.add( funcType->forall ); 1540 1541 // load type variables from arguments into one shared space 1542 for ( auto & arg : argsList ) { 1543 resultEnv.simpleCombine( arg->env ); 1544 } 1545 1546 // Make sure we don't widen any existing bindings 1547 resultEnv.forbidWidening(); 1548 1549 // Find any unbound type variables 1550 resultEnv.extractOpenVars( open ); 1551 1552 auto param = funcType->params.begin(); 1553 auto paramEnd = funcType->params.end(); 1554 1555 unsigned n_mutex_param = 0; 1556 1557 // For every argument of its set, check if it matches one of the 1558 // parameters. The order is important 1559 for ( auto & arg : argsList ) { 1560 // Ignore non-mutex arguments 1561 if ( ! nextMutex( param, paramEnd ) ) { 1562 // We ran out of parameters but still have arguments. 1563 // This function doesn't match 1564 SemanticError( stmt->location, funcType, 1565 toString("candidate function not viable: too many mutex " 1566 "arguments, expected ", n_mutex_param, "\n" ) ); 1567 } 1568 1569 ++n_mutex_param; 1570 1571 // Check if the argument matches the parameter type in the current 1572 // scope 1573 ast::ptr< ast::Type > paramType = (*param)->get_type(); 1574 if ( 1575 ! unify( 1576 arg->expr->result, paramType, resultEnv, need, have, open, 1577 symtab ) 1578 ) { 1579 // Type doesn't match 1580 stringstream ss; 1581 ss << "candidate function not viable: no known conversion " 1582 "from '"; 1583 ast::print( ss, (*param)->get_type() ); 1584 ss << "' to '"; 1585 ast::print( ss, arg->expr->result ); 1586 ss << "' with env '"; 1587 ast::print( ss, resultEnv ); 1588 ss << "'\n"; 1589 SemanticError( stmt->location, funcType, ss.str() ); 1590 } 1591 1592 ++param; 1593 } 1594 1595 // All arguments match! 1596 1597 // Check if parameters are missing 1598 if ( nextMutex( param, paramEnd ) ) { 1599 do { 1600 ++n_mutex_param; 1601 ++param; 1602 } while ( nextMutex( param, paramEnd ) ); 1603 1604 // We ran out of arguments but still have parameters left; this 1605 // function doesn't match 1606 SemanticError( stmt->location, funcType, 1607 toString( "candidate function not viable: too few mutex " 1608 "arguments, expected ", n_mutex_param, "\n" ) ); 1609 } 1610 1611 // All parameters match! 1612 1613 // Finish the expressions to tie in proper environments 1614 finishExpr( func2->expr, resultEnv ); 1615 for ( CandidateRef & arg : argsList ) { 1616 finishExpr( arg->expr, resultEnv ); 1617 } 1618 1619 // This is a match, store it and save it for later 1620 funcCandidates.emplace_back( std::move( func2 ) ); 1621 argsCandidates.emplace_back( std::move( argsList ) ); 1622 1623 } catch ( SemanticErrorException & e ) { 1624 errors.append( e ); 1625 } 1626 } 1627 } catch ( SemanticErrorException & e ) { 1628 errors.append( e ); 1629 } 1630 } 1631 1632 // Make sure correct number of arguments 1633 if( funcCandidates.empty() ) { 1634 SemanticErrorException top( stmt->location, 1635 "No alternatives for function in call to waitfor" ); 1636 top.append( errors ); 1637 throw top; 1638 } 1639 1640 if( argsCandidates.empty() ) { 1641 SemanticErrorException top( stmt->location, 1642 "No alternatives for arguments in call to waitfor" ); 1643 top.append( errors ); 1644 throw top; 1645 } 1646 1647 if( funcCandidates.size() > 1 ) { 1648 SemanticErrorException top( stmt->location, 1649 "Ambiguous function in call to waitfor" ); 1650 top.append( errors ); 1651 throw top; 1652 } 1653 if( argsCandidates.size() > 1 ) { 1654 SemanticErrorException top( stmt->location, 1655 "Ambiguous arguments in call to waitfor" ); 1656 top.append( errors ); 1657 throw top; 1658 } 1659 // TODO: need to use findDeletedExpr to ensure no deleted identifiers are used. 1660 1661 // build new clause 1662 ast::WaitForStmt::Clause clause2; 1663 1664 clause2.target.func = funcCandidates.front()->expr; 1665 1666 clause2.target.args.reserve( clause.target.args.size() ); 1667 for ( auto arg : argsCandidates.front() ) { 1668 clause2.target.args.emplace_back( std::move( arg->expr ) ); 1669 } 1670 1671 // Resolve the conditions as if it were an IfStmt, statements normally 1672 clause2.cond = findSingleExpression( clause.cond, symtab ); 1673 clause2.stmt = clause.stmt->accept( *visitor ); 1674 1675 // set results into stmt 1676 auto n = mutate( stmt ); 1677 n->clauses[i] = std::move( clause2 ); 1678 stmt = n; 1679 } 1680 1681 if ( stmt->timeout.stmt ) { 1682 // resolve the timeout as a size_t, the conditions like IfStmt, and stmts normally 1683 ast::WaitForStmt::Timeout timeout2; 1684 1685 ast::ptr< ast::Type > target = 1686 new ast::BasicType{ ast::BasicType::LongLongUnsignedInt }; 1687 timeout2.time = findSingleExpression( stmt->timeout.time, target, symtab ); 1688 timeout2.cond = findSingleExpression( stmt->timeout.cond, symtab ); 1689 timeout2.stmt = stmt->timeout.stmt->accept( *visitor ); 1690 1691 // set results into stmt 1692 auto n = mutate( stmt ); 1693 n->timeout = std::move( timeout2 ); 1694 stmt = n; 1695 } 1696 1697 if ( stmt->orElse.stmt ) { 1698 // resolve the condition like IfStmt, stmts normally 1699 ast::WaitForStmt::OrElse orElse2; 1700 1701 orElse2.cond = findSingleExpression( stmt->orElse.cond, symtab ); 1702 orElse2.stmt = stmt->orElse.stmt->accept( *visitor ); 1703 1704 // set results into stmt 1705 auto n = mutate( stmt ); 1706 n->orElse = std::move( orElse2 ); 1707 stmt = n; 1708 } 1709 1710 return stmt; 1451 1711 } 1452 1712 … … 1457 1717 // resolve initialization using the possibilities as determined by the `currentObject` 1458 1718 // cursor. 1459 ast:: Expr *untyped = new ast::UntypedInitExpr{1719 ast::ptr< ast::Expr > untyped = new ast::UntypedInitExpr{ 1460 1720 singleInit->location, singleInit->value, currentObject.getOptions() }; 1461 ast::ptr<ast::Expr> newExpr = find KindExpression( untyped, symtab );1721 ast::ptr<ast::Expr> newExpr = findSingleExpression( untyped, symtab ); 1462 1722 const ast::InitExpr * initExpr = newExpr.strict_as< ast::InitExpr >(); 1463 1723 -
src/ResolvExpr/Unify.cc
r6949c45 r2773ab8 1143 1143 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 1144 1144 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 1145 ast::OpenVarSet & open, const ast::SymbolTable & symtab 1146 ) { 1147 ast::ptr<ast::Type> common; 1148 return unify( type1, type2, env, need, have, open, symtab, common ); 1149 } 1150 1151 bool unify( 1152 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 1153 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 1145 1154 ast::OpenVarSet & open, const ast::SymbolTable & symtab, ast::ptr<ast::Type> & common 1146 1155 ) { -
src/ResolvExpr/Unify.h
r6949c45 r2773ab8 72 72 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 73 73 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 74 ast::OpenVarSet & open, const ast::SymbolTable & symtab ); 75 76 bool unify( 77 const ast::ptr<ast::Type> & type1, const ast::ptr<ast::Type> & type2, 78 ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, 74 79 ast::OpenVarSet & open, const ast::SymbolTable & symtab, ast::ptr<ast::Type> & common ); 75 80
Note: See TracChangeset
for help on using the changeset viewer.
