10.1 类型定义检查
主要解决:
- 包含void的数组，结构体，联合体
- 成员重复的结构，联合体
- 循环定义的结构，联合体-需要检查有没有引用闭环
class TypeChecker extends Visitor {
private final TypeTable typeTable;
private final ErrorHandler errorHandler;
// #@@range/ctor{
public TypeChecker(TypeTable typeTable, ErrorHandler errorHandler) {
this.typeTable = typeTable;
this.errorHandler = errorHandler;
}
// #@@}
private void check(StmtNode node) {
visitStmt(node);
}
private void check(ExprNode node) {
visitExpr(node);
}
// #@@range/check_AST{
DefinedFunction currentFunction;
public void check(AST ast) throws SemanticException {
for (DefinedVariable var : ast.definedVariables()) {
checkVariable(var);
}
for (DefinedFunction f : ast.definedFunctions()) {
currentFunction = f;
checkReturnType(f);
checkParamTypes(f);
check(f.body());
}
if (errorHandler.errorOccured()) {
throw new SemanticException("compile failed.");
}
}
// #@@}
private void checkReturnType(DefinedFunction f) {
if (isInvalidReturnType(f.returnType())) {
error(f.location(), "returns invalid type: " + f.returnType());
}
}
private void checkParamTypes(DefinedFunction f) {
for (CBCParameter param : f.parameters()) {
if (isInvalidParameterType(param.type())) {
error(param.location(),
"invalid parameter type: " + param.type());
}
}
}
//
// Statements
//
public Void visit(BlockNode node) {
for (DefinedVariable var : node.variables()) {
checkVariable(var);
}
for (StmtNode n : node.stmts()) {
check(n);
}
return null;
}
private void checkVariable(DefinedVariable var) {
if (isInvalidVariableType(var.type())) {
error(var.location(), "invalid variable type");
return;
}
if (var.hasInitializer()) {
if (isInvalidLHSType(var.type())) {
error(var.location(), "invalid LHS type: " + var.type());
return;
}
check(var.initializer());
var.setInitializer(implicitCast(var.type(), var.initializer()));
}
}
public Void visit(ExprStmtNode node) {
check(node.expr());
if (isInvalidStatementType(node.expr().type())) {
error(node, "invalid statement type: " + node.expr().type());
return null;
}
return null;
}
public Void visit(IfNode node) {
super.visit(node);
checkCond(node.cond());
return null;
}
public Void visit(WhileNode node) {
super.visit(node);
checkCond(node.cond());
return null;
}
public Void visit(ForNode node) {
super.visit(node);
checkCond(node.cond());
return null;
}
private void checkCond(ExprNode cond) {
mustBeScalar(cond, "condition expression");
}
public Void visit(SwitchNode node) {
super.visit(node);
mustBeInteger(node.cond(), "condition expression");
return null;
}
public Void visit(ReturnNode node) {
super.visit(node);
if (currentFunction.isVoid()) {
if (node.expr() != null) {
error(node, "returning value from void function");
}
}
else { // non-void function
if (node.expr() == null) {
error(node, "missing return value");
return null;
}
if (node.expr().type().isVoid()) {
error(node, "returning void");
return null;
}
node.setExpr(implicitCast(currentFunction.returnType(),
node.expr()));
}
return null;
}
//
// Assignment Expressions
//
public Void visit(AssignNode node) {
super.visit(node);
if (! checkLHS(node.lhs())) return null;
if (! checkRHS(node.rhs())) return null;
node.setRHS(implicitCast(node.lhs().type(), node.rhs()));
return null;
}
public Void visit(OpAssignNode node) {
super.visit(node);
if (! checkLHS(node.lhs())) return null;
if (! checkRHS(node.rhs())) return null;
if (node.operator().equals("+") || node.operator().equals("-")) {
if (node.lhs().type().isPointer()) {
mustBeInteger(node.rhs(), node.operator());
node.setRHS(integralPromotedExpr(node.rhs()));
return null;
}
}
if (! mustBeInteger(node.lhs(), node.operator())) return null;
if (! mustBeInteger(node.rhs(), node.operator())) return null;
Type l = integralPromotion(node.lhs().type());
Type r = integralPromotion(node.rhs().type());
Type opType = usualArithmeticConversion(l, r);
if (! opType.isCompatible(l)
&& ! isSafeIntegerCast(node.rhs(), opType)) {
warn(node, "incompatible implicit cast from "
+ opType + " to " + l);
}
if (! r.isSameType(opType)) {
// cast RHS
node.setRHS(new CastNode(opType, node.rhs()));
}
return null;
}
/** allow safe implicit cast from integer literal like:
*
* char c = 0;
*
* "0" has a type integer, but we can cast (int)0 to (char)0 safely.
*/
private boolean isSafeIntegerCast(Node node, Type type) {
if (! type.isInteger()) return false;
IntegerType t = (IntegerType)type;
if (! (node instanceof IntegerLiteralNode)) return false;
IntegerLiteralNode n = (IntegerLiteralNode)node;
return t.isInDomain(n.value());
}
private boolean checkLHS(ExprNode lhs) {
if (lhs.isParameter()) {
// parameter is always assignable.
return true;
}
else if (isInvalidLHSType(lhs.type())) {
error(lhs, "invalid LHS expression type: " + lhs.type());
return false;
}
return true;
}
//
// Expressions
//
public Void visit(CondExprNode node) {
super.visit(node);
checkCond(node.cond());
Type t = node.thenExpr().type();
Type e = node.elseExpr().type();
if (t.isSameType(e)) {
return null;
}
else if (t.isCompatible(e)) { // insert cast on thenBody
node.setThenExpr(new CastNode(e, node.thenExpr()));
}
else if (e.isCompatible(t)) { // insert cast on elseBody
node.setElseExpr(new CastNode(t, node.elseExpr()));
}
else {
invalidCastError(node.thenExpr(), e, t);
}
return null;
}
// #@@range/BinaryOpNode{
public Void visit(BinaryOpNode node) {
super.visit(node);
if (node.operator().equals("+") || node.operator().equals("-")) {
expectsSameIntegerOrPointerDiff(node);
}
else if (node.operator().equals("*")
|| node.operator().equals("/")
|| node.operator().equals("%")
|| node.operator().equals("&")
|| node.operator().equals("|")
|| node.operator().equals("^")
|| node.operator().equals("<<")
|| node.operator().equals(">>")) {
expectsSameInteger(node);
}
else if (node.operator().equals("==")
|| node.operator().equals("!=")
|| node.operator().equals("<")
|| node.operator().equals("<=")
|| node.operator().equals(">")
|| node.operator().equals(">=")) {
expectsComparableScalars(node);
}
else {
throw new Error("unknown binary operator: " + node.operator());
}
return null;
}
// #@@}
public Void visit(LogicalAndNode node) {
super.visit(node);
expectsComparableScalars(node);
return null;
}
public Void visit(LogicalOrNode node) {
super.visit(node);
expectsComparableScalars(node);
return null;
}
/**
* For + and -, only following types of expression are valid:
*
* * integer + integer
* * pointer + integer
* * integer + pointer
* * integer - integer
* * pointer - integer
* * pointer - pointer
*/
private void expectsSameIntegerOrPointerDiff(BinaryOpNode node) {
if (node.left().isPointer() && node.right().isPointer()) {
if (node.operator().equals("+")) {
error(node, "invalid operation: pointer + pointer");
return;
}
node.setType(typeTable.ptrDiffType());
}
else if (node.left().isPointer()) {
mustBeInteger(node.right(), node.operator());
// promote integer for pointer calculation
node.setRight(integralPromotedExpr(node.right()));
node.setType(node.left().type());
}
else if (node.right().isPointer()) {
if (node.operator().equals("-")) {
error(node, "invalid operation: integer - pointer");
return;
}
mustBeInteger(node.left(), node.operator());
// promote integer for pointer calculation
node.setLeft(integralPromotedExpr(node.left()));
node.setType(node.right().type());
}
else {
expectsSameInteger(node);
}
}
private ExprNode integralPromotedExpr(ExprNode expr) {
Type t = integralPromotion(expr.type());
if (t.isSameType(expr.type())) {
return expr;
}
else {
return new CastNode(t, expr);
}
}
// +, -, *, /, %, &, |, ^, <<, >>
// #@@range/expectsSameInteger{
private void expectsSameInteger(BinaryOpNode node) {
if (! mustBeInteger(node.left(), node.operator())) return;
if (! mustBeInteger(node.right(), node.operator())) return;
arithmeticImplicitCast(node);
}
// #@@}
// ==, !=, >, >=, <, <=, &&, ||
private void expectsComparableScalars(BinaryOpNode node) {
if (! mustBeScalar(node.left(), node.operator())) return;
if (! mustBeScalar(node.right(), node.operator())) return;
if (node.left().type().isPointer()) {
ExprNode right = forcePointerType(node.left(), node.right());
node.setRight(right);
node.setType(node.left().type());
return;
}
if (node.right().type().isPointer()) {
ExprNode left = forcePointerType(node.right(), node.left());
node.setLeft(left);
node.setType(node.right().type());
return;
}
arithmeticImplicitCast(node);
}
// cast slave node to master node.
private ExprNode forcePointerType(ExprNode master, ExprNode slave) {
if (master.type().isCompatible(slave.type())) {
// needs no cast
return slave;
}
else {
warn(slave, "incompatible implicit cast from "
+ slave.type() + " to " + master.type());
return new CastNode(master.type(), slave);
}
}
// Processes usual arithmetic conversion for binary operations.
// #@@range/arithmeticImplicitCast{
private void arithmeticImplicitCast(BinaryOpNode node) {
Type r = integralPromotion(node.right().type());
Type l = integralPromotion(node.left().type());
Type target = usualArithmeticConversion(l, r);
if (! l.isSameType(target)) {
// insert cast on left expr
node.setLeft(new CastNode(target, node.left()));
}
if (! r.isSameType(target)) {
// insert cast on right expr
node.setRight(new CastNode(target, node.right()));
}
node.setType(target);
}
// #@@}
// +, -, !, ~
public Void visit(UnaryOpNode node) {
super.visit(node);
if (node.operator().equals("!")) {
mustBeScalar(node.expr(), node.operator());
}
else {
mustBeInteger(node.expr(), node.operator());
}
return null;
}
// ++x, --x
public Void visit(PrefixOpNode node) {
super.visit(node);
expectsScalarLHS(node);
return null;
}
// x++, x--
public Void visit(SuffixOpNode node) {
super.visit(node);
expectsScalarLHS(node);
return null;
}
private void expectsScalarLHS(UnaryArithmeticOpNode node) {
if (node.expr().isParameter()) {
// parameter is always a scalar.
}
else if (node.expr().type().isArray()) {
// We cannot modify non-parameter array.
wrongTypeError(node.expr(), node.operator());
return;
}
else {
mustBeScalar(node.expr(), node.operator());
}
if (node.expr().type().isInteger()) {
Type opType = integralPromotion(node.expr().type());
if (! node.expr().type().isSameType(opType)) {
node.setOpType(opType);
}
node.setAmount(1);
}
else if (node.expr().type().isPointer()) {
if (node.expr().type().baseType().isVoid()) {
// We cannot increment/decrement void*
wrongTypeError(node.expr(), node.operator());
return;
}
node.setAmount(node.expr().type().baseType().size());
}
else {
throw new Error("must not happen");
}
}
/**
* For EXPR(ARG), checks:
*
* * The number of argument matches function prototype.
* * ARG matches function prototype.
* * ARG is neither a struct nor an union.
*/
public Void visit(FuncallNode node) {
super.visit(node);
FunctionType type = node.functionType();
if (! type.acceptsArgc(node.numArgs())) {
error(node, "wrong number of argments: " + node.numArgs());
return null;
}
Iterator<ExprNode> args = node.args().iterator();
List<ExprNode> newArgs = new ArrayList<ExprNode>();
// mandatory args
for (Type param : type.paramTypes()) {
ExprNode arg = args.next();
newArgs.add(checkRHS(arg) ? implicitCast(param, arg) : arg);
}
// optional args
while (args.hasNext()) {
ExprNode arg = args.next();
newArgs.add(checkRHS(arg) ? castOptionalArg(arg) : arg);
}
node.replaceArgs(newArgs);
return null;
}
private ExprNode castOptionalArg(ExprNode arg) {
if (! arg.type().isInteger()) {
return arg;
}
Type t = arg.type().isSigned()
? typeTable.signedStackType()
: typeTable.unsignedStackType();
return arg.type().size() < t.size() ? implicitCast(t, arg) : arg;
}
public Void visit(ArefNode node) {
super.visit(node);
mustBeInteger(node.index(), "[]");
return null;
}
public Void visit(CastNode node) {
super.visit(node);
if (! node.expr().type().isCastableTo(node.type())) {
invalidCastError(node, node.expr().type(), node.type());
}
return null;
}
//
// Utilities
//
private boolean checkRHS(ExprNode rhs) {
if (isInvalidRHSType(rhs.type())) {
error(rhs, "invalid RHS expression type: " + rhs.type());
return false;
}
return true;
}
// Processes forced-implicit-cast.
// Applied To: return expr, assignment RHS, funcall argument
private ExprNode implicitCast(Type targetType, ExprNode expr) {
if (expr.type().isSameType(targetType)) {
return expr;
}
else if (expr.type().isCastableTo(targetType)) {
if (! expr.type().isCompatible(targetType)
&& ! isSafeIntegerCast(expr, targetType)) {
warn(expr, "incompatible implicit cast from "
+ expr.type() + " to " + targetType);
}
return new CastNode(targetType, expr);
}
else {
invalidCastError(expr, expr.type(), targetType);
return expr;
}
}
// Process integral promotion (integers only).
// #@@range/integralPromotion{
private Type integralPromotion(Type t) {
if (!t.isInteger()) {
throw new Error("integralPromotion for " + t);
}
Type intType = typeTable.signedInt();
if (t.size() < intType.size()) {
return intType;
}
else {
return t;
}
}
// #@@}
// Usual arithmetic conversion for ILP32 platform (integers only).
// Size of l, r >= sizeof(int).
// #@@range/usualArithmeticConversion{
private Type usualArithmeticConversion(Type l, Type r) {
Type s_int = typeTable.signedInt();
Type u_int = typeTable.unsignedInt();
Type s_long = typeTable.signedLong();
Type u_long = typeTable.unsignedLong();
if ( (l.isSameType(u_int) && r.isSameType(s_long))
|| (r.isSameType(u_int) && l.isSameType(s_long))) {
return u_long;
}
else if (l.isSameType(u_long) || r.isSameType(u_long)) {
return u_long;
}
else if (l.isSameType(s_long) || r.isSameType(s_long)) {
return s_long;
}
else if (l.isSameType(u_int) || r.isSameType(u_int)) {
return u_int;
}
else {
return s_int;
}
}
// #@@}
private boolean isInvalidStatementType(Type t) {
return t.isStruct() || t.isUnion();
}
private boolean isInvalidReturnType(Type t) {
return t.isStruct() || t.isUnion() || t.isArray();
}
private boolean isInvalidParameterType(Type t) {
return t.isStruct() || t.isUnion() || t.isVoid()
|| t.isIncompleteArray();
}
private boolean isInvalidVariableType(Type t) {
return t.isVoid() || (t.isArray() && ! t.isAllocatedArray());
}
private boolean isInvalidLHSType(Type t) {
// Array is OK if it is declared as a type of parameter.
return t.isStruct() || t.isUnion() || t.isVoid() || t.isArray();
}
private boolean isInvalidRHSType(Type t) {
return t.isStruct() || t.isUnion() || t.isVoid();
}
private boolean mustBeInteger(ExprNode expr, String op) {
if (! expr.type().isInteger()) {
wrongTypeError(expr, op);
return false;
}
return true;
}
private boolean mustBeScalar(ExprNode expr, String op) {
if (! expr.type().isScalar()) {
wrongTypeError(expr, op);
return false;
}
return true;
}
private void invalidCastError(Node n, Type l, Type r) {
error(n, "invalid cast from " + l + " to " + r);
}
private void wrongTypeError(ExprNode expr, String op) {
error(expr, "wrong operand type for " + op + ": " + expr.type());
}
private void warn(Node n, String msg) {
errorHandler.warn(n.location(), msg);
}
private void error(Node n, String msg) {
errorHandler.error(n.location(), msg);
}
private void error(Location loc, String msg) {
errorHandler.error(loc, msg);
}
}