blob fccbad8b (19049B) - Raw
1 /* 2 * Copyright (c) 2015 Andrew Kelley 3 * 4 * This file is part of zig, which is MIT licensed. 5 * See http://opensource.org/licenses/MIT 6 */ 7 8 #include "analyze.hpp" 9 #include "semantic_info.hpp" 10 #include "error.hpp" 11 #include "zig_llvm.hpp" 12 #include "os.hpp" 13 14 static void add_node_error(CodeGen *g, AstNode *node, Buf *msg) { 15 ErrorMsg *err = allocate<ErrorMsg>(1); 16 err->line_start = node->line; 17 err->column_start = node->column; 18 err->line_end = -1; 19 err->column_end = -1; 20 err->msg = msg; 21 err->path = node->owner->path; 22 err->source = node->owner->source_code; 23 err->line_offsets = node->owner->line_offsets; 24 25 g->errors.append(err); 26 } 27 28 static int parse_version_string(Buf *buf, int *major, int *minor, int *patch) { 29 char *dot1 = strstr(buf_ptr(buf), "."); 30 if (!dot1) 31 return ErrorInvalidFormat; 32 char *dot2 = strstr(dot1 + 1, "."); 33 if (!dot2) 34 return ErrorInvalidFormat; 35 36 *major = (int)strtol(buf_ptr(buf), nullptr, 10); 37 *minor = (int)strtol(dot1 + 1, nullptr, 10); 38 *patch = (int)strtol(dot2 + 1, nullptr, 10); 39 40 return ErrorNone; 41 } 42 43 static void set_root_export_version(CodeGen *g, Buf *version_buf, AstNode *node) { 44 int err; 45 if ((err = parse_version_string(version_buf, &g->version_major, &g->version_minor, &g->version_patch))) { 46 add_node_error(g, node, 47 buf_sprintf("invalid version string")); 48 } 49 } 50 51 static void resolve_type(CodeGen *g, AstNode *node) { 52 assert(!node->codegen_node); 53 node->codegen_node = allocate<CodeGenNode>(1); 54 TypeNode *type_node = &node->codegen_node->data.type_node; 55 switch (node->data.type.type) { 56 case AstNodeTypeTypePrimitive: 57 { 58 Buf *name = &node->data.type.primitive_name; 59 auto table_entry = g->type_table.maybe_get(name); 60 if (table_entry) { 61 type_node->entry = table_entry->value; 62 } else { 63 add_node_error(g, node, 64 buf_sprintf("invalid type name: '%s'", buf_ptr(name))); 65 type_node->entry = g->builtin_types.entry_invalid; 66 } 67 break; 68 } 69 case AstNodeTypeTypePointer: 70 { 71 resolve_type(g, node->data.type.child_type); 72 TypeNode *child_type_node = &node->data.type.child_type->codegen_node->data.type_node; 73 if (child_type_node->entry == g->builtin_types.entry_unreachable) { 74 add_node_error(g, node, 75 buf_create_from_str("pointer to unreachable not allowed")); 76 } 77 TypeTableEntry **parent_pointer = node->data.type.is_const ? 78 &child_type_node->entry->pointer_const_parent : 79 &child_type_node->entry->pointer_mut_parent; 80 const char *const_or_mut_str = node->data.type.is_const ? "const" : "mut"; 81 if (*parent_pointer) { 82 type_node->entry = *parent_pointer; 83 } else { 84 TypeTableEntry *entry = allocate<TypeTableEntry>(1); 85 entry->type_ref = LLVMPointerType(child_type_node->entry->type_ref, 0); 86 buf_resize(&entry->name, 0); 87 buf_appendf(&entry->name, "*%s %s", const_or_mut_str, buf_ptr(&child_type_node->entry->name)); 88 entry->di_type = LLVMZigCreateDebugPointerType(g->dbuilder, child_type_node->entry->di_type, 89 g->pointer_size_bytes * 8, g->pointer_size_bytes * 8, buf_ptr(&entry->name)); 90 g->type_table.put(&entry->name, entry); 91 type_node->entry = entry; 92 *parent_pointer = entry; 93 } 94 break; 95 } 96 } 97 } 98 99 static void resolve_function_proto(CodeGen *g, AstNode *node) { 100 assert(node->type == NodeTypeFnProto); 101 102 for (int i = 0; i < node->data.fn_proto.directives->length; i += 1) { 103 AstNode *directive_node = node->data.fn_proto.directives->at(i); 104 Buf *name = &directive_node->data.directive.name; 105 add_node_error(g, directive_node, 106 buf_sprintf("invalid directive: '%s'", buf_ptr(name))); 107 } 108 109 for (int i = 0; i < node->data.fn_proto.params.length; i += 1) { 110 AstNode *child = node->data.fn_proto.params.at(i); 111 assert(child->type == NodeTypeParamDecl); 112 113 // parameter names are not important here. 114 115 resolve_type(g, child->data.param_decl.type); 116 } 117 118 resolve_type(g, node->data.fn_proto.return_type); 119 } 120 121 static void preview_function_declarations(CodeGen *g, ImportTableEntry *import, AstNode *node) { 122 switch (node->type) { 123 case NodeTypeExternBlock: 124 for (int i = 0; i < node->data.extern_block.directives->length; i += 1) { 125 AstNode *directive_node = node->data.extern_block.directives->at(i); 126 Buf *name = &directive_node->data.directive.name; 127 Buf *param = &directive_node->data.directive.param; 128 if (buf_eql_str(name, "link")) { 129 g->link_table.put(param, true); 130 } else { 131 add_node_error(g, directive_node, 132 buf_sprintf("invalid directive: '%s'", buf_ptr(name))); 133 } 134 } 135 136 for (int fn_decl_i = 0; fn_decl_i < node->data.extern_block.fn_decls.length; fn_decl_i += 1) { 137 AstNode *fn_decl = node->data.extern_block.fn_decls.at(fn_decl_i); 138 assert(fn_decl->type == NodeTypeFnDecl); 139 AstNode *fn_proto = fn_decl->data.fn_decl.fn_proto; 140 resolve_function_proto(g, fn_proto); 141 Buf *name = &fn_proto->data.fn_proto.name; 142 143 FnTableEntry *fn_table_entry = allocate<FnTableEntry>(1); 144 fn_table_entry->proto_node = fn_proto; 145 fn_table_entry->is_extern = true; 146 fn_table_entry->calling_convention = LLVMCCallConv; 147 fn_table_entry->import_entry = import; 148 g->fn_table.put(name, fn_table_entry); 149 } 150 break; 151 case NodeTypeFnDef: 152 { 153 AstNode *proto_node = node->data.fn_def.fn_proto; 154 assert(proto_node->type == NodeTypeFnProto); 155 Buf *proto_name = &proto_node->data.fn_proto.name; 156 auto entry = g->fn_table.maybe_get(proto_name); 157 if (entry) { 158 add_node_error(g, node, 159 buf_sprintf("redefinition of '%s'", buf_ptr(proto_name))); 160 assert(!node->codegen_node); 161 node->codegen_node = allocate<CodeGenNode>(1); 162 node->codegen_node->data.fn_def_node.skip = true; 163 } else { 164 FnTableEntry *fn_table_entry = allocate<FnTableEntry>(1); 165 fn_table_entry->import_entry = import; 166 fn_table_entry->proto_node = proto_node; 167 fn_table_entry->fn_def_node = node; 168 fn_table_entry->internal_linkage = proto_node->data.fn_proto.visib_mod != FnProtoVisibModExport; 169 if (fn_table_entry->internal_linkage) { 170 fn_table_entry->calling_convention = LLVMFastCallConv; 171 } else { 172 fn_table_entry->calling_convention = LLVMCCallConv; 173 } 174 g->fn_table.put(proto_name, fn_table_entry); 175 g->fn_defs.append(fn_table_entry); 176 177 resolve_function_proto(g, proto_node); 178 } 179 } 180 break; 181 case NodeTypeRootExportDecl: 182 if (import == g->root_import) { 183 for (int i = 0; i < node->data.root_export_decl.directives->length; i += 1) { 184 AstNode *directive_node = node->data.root_export_decl.directives->at(i); 185 Buf *name = &directive_node->data.directive.name; 186 Buf *param = &directive_node->data.directive.param; 187 if (buf_eql_str(name, "version")) { 188 set_root_export_version(g, param, directive_node); 189 } else { 190 add_node_error(g, directive_node, 191 buf_sprintf("invalid directive: '%s'", buf_ptr(name))); 192 } 193 } 194 195 if (g->root_export_decl) { 196 add_node_error(g, node, 197 buf_sprintf("only one root export declaration allowed")); 198 } else { 199 g->root_export_decl = node; 200 201 if (!g->root_out_name) 202 g->root_out_name = &node->data.root_export_decl.name; 203 204 Buf *out_type = &node->data.root_export_decl.type; 205 OutType export_out_type; 206 if (buf_eql_str(out_type, "executable")) { 207 export_out_type = OutTypeExe; 208 } else if (buf_eql_str(out_type, "library")) { 209 export_out_type = OutTypeLib; 210 } else if (buf_eql_str(out_type, "object")) { 211 export_out_type = OutTypeObj; 212 } else { 213 add_node_error(g, node, 214 buf_sprintf("invalid export type: '%s'", buf_ptr(out_type))); 215 } 216 if (g->out_type == OutTypeUnknown) 217 g->out_type = export_out_type; 218 } 219 } else { 220 add_node_error(g, node, 221 buf_sprintf("root export declaration only valid in root source file")); 222 } 223 break; 224 case NodeTypeUse: 225 // nothing to do here 226 break; 227 case NodeTypeDirective: 228 case NodeTypeParamDecl: 229 case NodeTypeFnProto: 230 case NodeTypeType: 231 case NodeTypeFnDecl: 232 case NodeTypeReturnExpr: 233 case NodeTypeRoot: 234 case NodeTypeBlock: 235 case NodeTypeBinOpExpr: 236 case NodeTypeFnCallExpr: 237 case NodeTypeNumberLiteral: 238 case NodeTypeStringLiteral: 239 case NodeTypeUnreachable: 240 case NodeTypeSymbol: 241 case NodeTypeCastExpr: 242 case NodeTypePrefixOpExpr: 243 zig_unreachable(); 244 } 245 } 246 247 static void check_fn_def_control_flow(CodeGen *g, AstNode *node) { 248 // Follow the execution flow and make sure the code returns appropriately. 249 // * A `return` statement in an unreachable type function should be an error. 250 // * Control flow should not be able to reach the end of an unreachable type function. 251 // * Functions that have a type other than void should not return without a value. 252 // * void functions without explicit return statements at the end need the 253 // add_implicit_return flag set on the codegen node. 254 assert(node->type == NodeTypeFnDef); 255 AstNode *proto_node = node->data.fn_def.fn_proto; 256 assert(proto_node->type == NodeTypeFnProto); 257 AstNode *return_type_node = proto_node->data.fn_proto.return_type; 258 assert(return_type_node->type == NodeTypeType); 259 260 node->codegen_node = allocate<CodeGenNode>(1); 261 FnDefNode *codegen_fn_def = &node->codegen_node->data.fn_def_node; 262 263 assert(return_type_node->codegen_node); 264 TypeTableEntry *type_entry = return_type_node->codegen_node->data.type_node.entry; 265 assert(type_entry); 266 267 AstNode *body_node = node->data.fn_def.body; 268 assert(body_node->type == NodeTypeBlock); 269 270 // TODO once we understand types, do this pass after type checking, and 271 // if an expression has an unreachable value then stop looking at statements after 272 // it. then we can remove the check to `unreachable` in the end of this function. 273 bool prev_statement_return = false; 274 for (int i = 0; i < body_node->data.block.statements.length; i += 1) { 275 AstNode *statement_node = body_node->data.block.statements.at(i); 276 if (statement_node->type == NodeTypeReturnExpr) { 277 if (type_entry == g->builtin_types.entry_unreachable) { 278 add_node_error(g, statement_node, 279 buf_sprintf("return statement in function with unreachable return type")); 280 return; 281 } else { 282 prev_statement_return = true; 283 } 284 } else if (prev_statement_return) { 285 add_node_error(g, statement_node, 286 buf_sprintf("unreachable code")); 287 } 288 } 289 290 if (!prev_statement_return) { 291 if (type_entry == g->builtin_types.entry_void) { 292 codegen_fn_def->add_implicit_return = true; 293 } else if (type_entry != g->builtin_types.entry_unreachable) { 294 add_node_error(g, node, 295 buf_sprintf("control reaches end of non-void function")); 296 } 297 } 298 } 299 300 static void analyze_expression(CodeGen *g, AstNode *node) { 301 switch (node->type) { 302 case NodeTypeBlock: 303 for (int i = 0; i < node->data.block.statements.length; i += 1) { 304 AstNode *child = node->data.block.statements.at(i); 305 analyze_expression(g, child); 306 } 307 break; 308 case NodeTypeReturnExpr: 309 if (node->data.return_expr.expr) { 310 analyze_expression(g, node->data.return_expr.expr); 311 } 312 break; 313 case NodeTypeBinOpExpr: 314 analyze_expression(g, node->data.bin_op_expr.op1); 315 analyze_expression(g, node->data.bin_op_expr.op2); 316 break; 317 case NodeTypeFnCallExpr: 318 { 319 Buf *name = hack_get_fn_call_name(g, node->data.fn_call_expr.fn_ref_expr); 320 321 auto entry = g->fn_table.maybe_get(name); 322 if (!entry) { 323 add_node_error(g, node, 324 buf_sprintf("undefined function: '%s'", buf_ptr(name))); 325 } else { 326 FnTableEntry *fn_table_entry = entry->value; 327 assert(fn_table_entry->proto_node->type == NodeTypeFnProto); 328 int expected_param_count = fn_table_entry->proto_node->data.fn_proto.params.length; 329 int actual_param_count = node->data.fn_call_expr.params.length; 330 if (expected_param_count != actual_param_count) { 331 add_node_error(g, node, 332 buf_sprintf("wrong number of arguments. Expected %d, got %d.", 333 expected_param_count, actual_param_count)); 334 } 335 } 336 337 for (int i = 0; i < node->data.fn_call_expr.params.length; i += 1) { 338 AstNode *child = node->data.fn_call_expr.params.at(i); 339 analyze_expression(g, child); 340 } 341 break; 342 } 343 case NodeTypeCastExpr: 344 zig_panic("TODO"); 345 break; 346 case NodeTypePrefixOpExpr: 347 zig_panic("TODO"); 348 break; 349 case NodeTypeNumberLiteral: 350 case NodeTypeStringLiteral: 351 case NodeTypeUnreachable: 352 case NodeTypeSymbol: 353 // nothing to do 354 break; 355 case NodeTypeDirective: 356 case NodeTypeFnDecl: 357 case NodeTypeFnProto: 358 case NodeTypeParamDecl: 359 case NodeTypeType: 360 case NodeTypeRoot: 361 case NodeTypeRootExportDecl: 362 case NodeTypeExternBlock: 363 case NodeTypeFnDef: 364 case NodeTypeUse: 365 zig_unreachable(); 366 } 367 } 368 369 static void analyze_top_level_declaration(CodeGen *g, AstNode *node) { 370 switch (node->type) { 371 case NodeTypeFnDef: 372 { 373 if (node->codegen_node && node->codegen_node->data.fn_def_node.skip) { 374 // we detected an error with this function definition which prevents us 375 // from further analyzing it. 376 break; 377 } 378 379 AstNode *fn_proto_node = node->data.fn_def.fn_proto; 380 assert(fn_proto_node->type == NodeTypeFnProto); 381 382 AstNodeFnProto *fn_proto = &fn_proto_node->data.fn_proto; 383 for (int i = 0; i < fn_proto->params.length; i += 1) { 384 AstNode *param_decl_node = fn_proto->params.at(i); 385 assert(param_decl_node->type == NodeTypeParamDecl); 386 // TODO: define local variables for parameters 387 } 388 389 check_fn_def_control_flow(g, node); 390 analyze_expression(g, node->data.fn_def.body); 391 } 392 break; 393 394 case NodeTypeRootExportDecl: 395 case NodeTypeExternBlock: 396 // already looked at these in the preview pass 397 break; 398 case NodeTypeUse: 399 for (int i = 0; i < node->data.use.directives->length; i += 1) { 400 AstNode *directive_node = node->data.use.directives->at(i); 401 Buf *name = &directive_node->data.directive.name; 402 add_node_error(g, directive_node, 403 buf_sprintf("invalid directive: '%s'", buf_ptr(name))); 404 } 405 break; 406 case NodeTypeDirective: 407 case NodeTypeParamDecl: 408 case NodeTypeFnProto: 409 case NodeTypeType: 410 case NodeTypeFnDecl: 411 case NodeTypeReturnExpr: 412 case NodeTypeRoot: 413 case NodeTypeBlock: 414 case NodeTypeBinOpExpr: 415 case NodeTypeFnCallExpr: 416 case NodeTypeNumberLiteral: 417 case NodeTypeStringLiteral: 418 case NodeTypeUnreachable: 419 case NodeTypeSymbol: 420 case NodeTypeCastExpr: 421 case NodeTypePrefixOpExpr: 422 zig_unreachable(); 423 } 424 } 425 426 static void analyze_root(CodeGen *g, ImportTableEntry *import, AstNode *node) { 427 assert(node->type == NodeTypeRoot); 428 429 // find function declarations 430 for (int i = 0; i < node->data.root.top_level_decls.length; i += 1) { 431 AstNode *child = node->data.root.top_level_decls.at(i); 432 preview_function_declarations(g, import, child); 433 } 434 435 for (int i = 0; i < node->data.root.top_level_decls.length; i += 1) { 436 AstNode *child = node->data.root.top_level_decls.at(i); 437 analyze_top_level_declaration(g, child); 438 } 439 440 } 441 442 void semantic_analyze(CodeGen *g) { 443 auto it = g->import_table.entry_iterator(); 444 for (;;) { 445 auto *entry = it.next(); 446 if (!entry) 447 break; 448 449 ImportTableEntry *import = entry->value; 450 analyze_root(g, import, import->root); 451 } 452 453 if (!g->root_out_name) { 454 add_node_error(g, g->root_import->root, 455 buf_sprintf("missing export declaration and output name not provided")); 456 } else if (g->out_type == OutTypeUnknown) { 457 add_node_error(g, g->root_import->root, 458 buf_sprintf("missing export declaration and export type not provided")); 459 } 460 }