From 4baf0dedce1a17b8e3158165d397bb68747c9b11 Mon Sep 17 00:00:00 2001 From: Jean Privat Date: Thu, 12 Apr 2012 11:45:48 -0400 Subject: [PATCH] model: new metamodel This commit introduces a new metamodel. I expect it is simpler than the current one. A new modelbuilder and typing is also provided. As a proof of concept two tools are included: nit and nitstats nit is a basic naive and inefficient interpreter. nitstats is a tool to collect and gather some statistics. Signed-off-by: Jean Privat --- src/auto_super_init.nit | 133 ++++ src/exprbuilder.nit | 69 ++ src/flow.nit | 552 ++++++++++++++++ src/literal.nit | 146 +++++ src/local_var_init.nit | 145 +++++ src/model/model.nit | 1454 ++++++++++++++++++++++++++++++++++++++++++ src/model/model_base.nit | 291 +++++++++ src/modelbuilder.nit | 1401 ++++++++++++++++++++++++++++++++++++++++ src/naiveinterpreter.nit | 1409 ++++++++++++++++++++++++++++++++++++++++ src/nit.nit | 53 ++ src/nitstats.nit | 577 +++++++++++++++++ src/parser/parser.nit | 1 + src/parser/xss/main.xss | 1 + src/poset.nit | 223 +++++++ src/runtime_type.nit | 561 ++++++++++++++++ src/scope.nit | 448 +++++++++++++ src/simple_misc_analysis.nit | 176 +++++ src/typing.nit | 1448 +++++++++++++++++++++++++++++++++++++++++ 18 files changed, 9088 insertions(+) create mode 100644 src/auto_super_init.nit create mode 100644 src/exprbuilder.nit create mode 100644 src/flow.nit create mode 100644 src/literal.nit create mode 100644 src/local_var_init.nit create mode 100644 src/model/model.nit create mode 100644 src/model/model_base.nit create mode 100644 src/modelbuilder.nit create mode 100644 src/naiveinterpreter.nit create mode 100644 src/nit.nit create mode 100644 src/nitstats.nit create mode 100644 src/poset.nit create mode 100644 src/runtime_type.nit create mode 100644 src/scope.nit create mode 100644 src/simple_misc_analysis.nit create mode 100644 src/typing.nit diff --git a/src/auto_super_init.nit b/src/auto_super_init.nit new file mode 100644 index 0000000..d939740 --- /dev/null +++ b/src/auto_super_init.nit @@ -0,0 +1,133 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Computing of super-constructors that must be implicitely called at the begin of constructors. +# The current rules are a bit crazy but whatever. +module auto_super_init + +import typing +import modelbuilder + +private class AutoSuperInitVisitor + super Visitor + init + do + end + + redef fun visit(n) + do + if n == null then return + n.accept_auto_super_init(self) + n.visit_all(self) + end + + var has_explicit_super_init: Bool = false +end + + +redef class AConcreteMethPropdef + # In case of constructor, the list of implicit auto super init constructors invoked (if needed) + var auto_super_inits: nullable Array[MMethod] = null + + fun do_auto_super_init(modelbuilder: ModelBuilder) + do + var mclassdef = self.parent.as(AClassdef).mclassdef.as(not null) + var mpropdef = self.mpropdef.as(not null) + var mmodule = mpropdef.mclassdef.mmodule + + # Collect only for constructors + if not mpropdef.mproperty.is_init then return + + # FIXME: THIS IS STUPID (be here to keep the old code working) + if not mpropdef.mclassdef.is_intro then return + + # Do we inherit for a constructor? + var skip = true + for cd in mclassdef.in_hierarchy.direct_greaters do + if cd.mclass.kind.need_init then skip = false + end + if skip then return + + # Now we search for the absence of any explicit super-init invocation + # * via a "super" + # * via a call of an other init + var nblock = self.n_block + if nblock != null then + var v = new AutoSuperInitVisitor + v.enter_visit(nblock) + if v.has_explicit_super_init then return + end + + # Still here? So it means that we must determine what super inits need to be automatically invoked + + var auto_super_inits = new Array[MMethod] + for msupertype in mclassdef.supertypes do + # FIXME: the order is quite arbitrary + if not msupertype.mclass.kind.need_init then continue + msupertype = msupertype.anchor_to(mmodule, mclassdef.bound_mtype) + var candidate = modelbuilder.try_get_mproperty_by_name2(self, mmodule, msupertype, mpropdef.mproperty.name) + if candidate == null then + candidate = modelbuilder.try_get_mproperty_by_name2(self, mmodule, msupertype, "init") + end + if candidate == null then + modelbuilder.error(self, "Cannot do an implicit constructor call for {mpropdef}: there is no costructor named {mpropdef.mproperty.name} in {msupertype}.") + return + end + assert candidate isa MMethod + auto_super_inits.add(candidate) + end + if auto_super_inits.is_empty then + modelbuilder.error(self, "No constructors to call implicitely. Call one explicitely.") + return + end + for auto_super_init in auto_super_inits do + var auto_super_init_def = auto_super_init.intro + var msig = mpropdef.msignature.as(not null) + var supermsig = auto_super_init_def.msignature.as(not null) + if auto_super_init_def.msignature.arity != 0 and auto_super_init_def.msignature.arity != mpropdef.msignature.arity then + # TODO: Better check of the signature + modelbuilder.error(self, "Problem with signature of constructor {auto_super_init_def}{supermsig}. Expected {msig}") + end + end + self.auto_super_inits = auto_super_inits + end + +end + +redef class ANode + private fun accept_auto_super_init(v: AutoSuperInitVisitor) do end +end + + +redef class ASendExpr + redef fun accept_auto_super_init(v) + do + var mproperty = self.mproperty + if mproperty == null then return + if mproperty.is_init then + v.has_explicit_super_init = true + end + end +end + +redef class ASuperExpr + redef fun accept_auto_super_init(v) + do + # If the super is a standard call-next-method then there it is considered am explicit super init call + # The the super is a "super int" then it is also an explicit super init call + v.has_explicit_super_init = true + end +end diff --git a/src/exprbuilder.nit b/src/exprbuilder.nit new file mode 100644 index 0000000..05175e5 --- /dev/null +++ b/src/exprbuilder.nit @@ -0,0 +1,69 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Semantic analysis of the body of property definitions. +# +# This module is an entry point for various analysis. +# +# FIXME: find a better name for the module +module exprbuilder + +import simple_misc_analysis +import literal +import scope +import flow +import local_var_init +import typing +import auto_super_init + +redef class ModelBuilder + # Run the full_semantic_analysis on all propdefs of all modules + fun full_propdef_semantic_analysis + do + var time0 = get_time + self.toolcontext.info("*** SEMANTIC ANALYSIS ***", 1) + for nmodule in self.nmodules do + nmodule.do_simple_misc_analysis(self.toolcontext) + nmodule.do_literal(self.toolcontext) + for nclassdef in nmodule.n_classdefs do + for npropdef in nclassdef.n_propdefs do + npropdef.full_semantic_analysis(self) + end + end + self.toolcontext.check_errors + end + var time1 = get_time + self.toolcontext.info("*** END SEMANTIC ANALYSIS: {time1-time0} ***", 2) + end +end + +redef class APropdef + # Run do_scope, do_flow, do_local_var_init and do_typing + fun full_semantic_analysis(modelbuilder: ModelBuilder) + do + modelbuilder.toolcontext.info("* SEMANTIC ANALYSIS: {self.location}", 3) + var errcount = modelbuilder.toolcontext.error_count + do_scope(modelbuilder.toolcontext) + if errcount != modelbuilder.toolcontext.error_count then return + do_flow(modelbuilder.toolcontext) + if errcount != modelbuilder.toolcontext.error_count then return + do_local_var_init(modelbuilder.toolcontext) + if errcount != modelbuilder.toolcontext.error_count then return + do_typing(modelbuilder) + if errcount != modelbuilder.toolcontext.error_count then return + if self isa AConcreteMethPropdef then self.do_auto_super_init(modelbuilder) + end +end diff --git a/src/flow.nit b/src/flow.nit new file mode 100644 index 0000000..7846ee1 --- /dev/null +++ b/src/flow.nit @@ -0,0 +1,552 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Intraprocedural static flow. +module flow + +import parser +import toolcontext +import scope + +# The visitor that derermine flowcontext for nodes +private class FlowVisitor + super Visitor + + var current_flow_context: FlowContext + + var toolcontext: ToolContext + + init(toolcontext: ToolContext) + do + self.toolcontext = toolcontext + current_flow_context = new FlowContext + flows.add(current_flow_context) + current_flow_context.is_start = true + end + + var first: nullable ANode + + redef fun visit(node) + do + if node != null then + if first == null then first = node + + if current_flow_context.node == null then current_flow_context.node = node + node.accept_flow_visitor(self) + if node isa AExpr then + var flow = self.current_flow_context + node.after_flow_context = flow + if flow.when_true != flow or flow.when_false != flow then + #self.make_sub_flow + end + end + + if first == node then + #self.printflow + end + end + end + + fun visit_expr(node: AExpr): FlowContext + do + self.visit(node) + return node.after_flow_context.as(not null) + end + + var flows: Array[FlowContext] = new Array[FlowContext] + + fun printflow + do + var file = new OFStream.open("flow.dot") + file.write("digraph \{\n") + for f in flows do + var s = "" + if f.node isa AExpr then + s = "\\nmain={f.node.as(AExpr).after_flow_context.object_id}" + end + file.write "F{f.object_id} [label=\"{f.object_id}\\n{f.node.location}\\n{f.node.class_name}\\n{f.name}{s}\"];\n" + for p in f.previous do + file.write "F{p.object_id} -> F{f.object_id};\n" + end + if f.when_true != f then + file.write "F{f.object_id} -> F{f.when_true.object_id}[label=TRUE, style=dotted];\n" + end + if f.when_false != f then + file.write "F{f.object_id} -> F{f.when_false.object_id}[label=FALSE,style=dotted];\n" + end + end + file.write("\n") + file.close + end + + + fun make_sub_flow: FlowContext + do + var flow = new FlowContext + flows.add(flow) + flow.node = current_node + flow.add_previous(self.current_flow_context) + self.current_flow_context = flow + return flow + end + + fun make_merge_flow(flow1, flow2: FlowContext): FlowContext + do + var flow = new FlowContext + flows.add(flow) + flow.node = current_node + flow.add_previous(flow1) + flow.add_previous(flow2) + self.current_flow_context = flow + return flow + end + + fun make_true_false_flow(true_flow, false_flow: FlowContext): FlowContext + do + var flow = new FlowContext + flows.add(flow) + flow.node = current_node + flow.add_previous(true_flow) + flow.add_previous(false_flow) + flow.when_true = true_flow + flow.when_false = false_flow + self.current_flow_context = flow + return flow + end + + fun make_sub_true_false_flow: FlowContext + do + var orig_flow = self.current_flow_context + var true_flow = new FlowContext + flows.add(true_flow) + true_flow.node = current_node + true_flow.add_previous(orig_flow) + true_flow.name = "TRUE" + var false_flow = new FlowContext + flows.add(false_flow) + false_flow.node = current_node + false_flow.add_previous(orig_flow) + false_flow.name = "FALSE" + return make_true_false_flow(true_flow, false_flow) + end + + fun make_unreachable_flow: FlowContext + do + var flow = new FlowContext + flows.add(flow) + flow.node = current_node + flow.add_previous(self.current_flow_context) + flow.is_marked_unreachable = true + self.current_flow_context = flow + return flow + end + + fun merge_continues_to(before_loop: FlowContext, escapemark: nullable EscapeMark) + do + if escapemark == null then return + for b in escapemark.continues do + var before = b.before_flow_context + if before == null then continue # Forward error + before_loop.add_loop(before) + end + end + + fun merge_breaks(escapemark: nullable EscapeMark) + do + if escapemark == null then return + for b in escapemark.breaks do + var before = b.before_flow_context + if before == null then continue # Forward error + self.make_merge_flow(self.current_flow_context, before) + end + end +end + +# A Node in the static flow graph. +# A same FlowContext can be shared by more than one ANode. +class FlowContext + # The reachable previous flow + var previous: Array[FlowContext] = new Array[FlowContext] + + # Additional reachable flow that loop up to self. + # Loops apears in 'loop', 'while', 'for', closure and with 'continue' + var loops: Array[FlowContext] = new Array[FlowContext] + + private var is_marked_unreachable: Bool = false + + # Is the flow dead? + fun is_unreachable: Bool + do + # Are we explicitely marked unreachable? + if self.is_marked_unreachable then return true + + # Are we the starting flow context? + if is_start then return false + + # De we have a reachable previous? + if previous.length == 0 then return true + return false + end + + # Flag to avoid repeaed errors + var is_already_unreachable: Bool = false + + # Mark that self is the starting flow context. + # Such a context is reachable even if there is no previous flow + var is_start: Bool = false + + # The node that introduce the flow (for debuging) + var node: nullable ANode = null + + # Additional information for the flor (for debuging) + var name: String = "" + + # The sub-flow to use if the associated expr is true + var when_true: FlowContext = self + + # The sub-flow to use if the associated expr is true + var when_false: FlowContext = self + + # Add a previous flow (iff it is reachable) + private fun add_previous(flow: FlowContext) + do + if not flow.is_unreachable and not previous.has(flow) then + previous.add(flow) + end + end + + # Add a previous loop flow (iff it is reachable) + private fun add_loop(flow: FlowContext) + do + if not flow.is_unreachable and not previous.has(flow) then + loops.add(flow) + end + end + +end + +redef class ANode + private fun accept_flow_visitor(v: FlowVisitor) + do + self.visit_all(v) + end +end + +redef class APropdef + # The entry point of the whole flow analysis + fun do_flow(toolcontext: ToolContext) + do + var v = new FlowVisitor(toolcontext) + v.enter_visit(self) + end + + + # The starting flow + var before_flow_context: nullable FlowContext + + # The ending flow + var after_flow_context: nullable FlowContext + + redef fun accept_flow_visitor(v) + do + self.before_flow_context = v.current_flow_context + super + self.after_flow_context = v.current_flow_context + end +end + +redef class AExpr + # The flow after the full evaluation of the expression/statement + var after_flow_context: nullable FlowContext +end + +redef class AVarAssignExpr + redef fun accept_flow_visitor(v) + do + super + self.after_flow_context = v.make_sub_flow + end +end + +redef class AReassignFormExpr + redef fun accept_flow_visitor(v) + do + super + self.after_flow_context = v.make_sub_flow + end +end + +redef class ABlockExpr + redef fun accept_flow_visitor(v) + do + for e in n_expr do + if not v.current_flow_context.is_unreachable then + v.enter_visit(e) + else if not v.current_flow_context.is_already_unreachable then + v.current_flow_context.is_already_unreachable = true + v.toolcontext.error(e.hot_location, "Error: unreachable statement.") + end + end + end +end + +redef class AReturnExpr + redef fun accept_flow_visitor(v) + do + super + v.make_unreachable_flow + end +end + +redef class AContinueExpr + # The flow just before it become unreachable + fun before_flow_context: nullable FlowContext + do + var after = self.after_flow_context + if after == null then return null + return after.previous.first + end + redef fun accept_flow_visitor(v) + do + super + v.make_unreachable_flow + end +end + +redef class ABreakExpr + # The flow just before it become unreachable + fun before_flow_context: nullable FlowContext + do + var after = self.after_flow_context + if after == null then return null + return after.previous.first + end + redef fun accept_flow_visitor(v) + do + super + v.make_unreachable_flow + end +end + +redef class AAbortExpr + redef fun accept_flow_visitor(v) + do + super + v.make_unreachable_flow + end +end + +redef class ADoExpr + redef fun accept_flow_visitor(v) + do + super + v.merge_breaks(self.escapemark) + end +end + +redef class AIfExpr + redef fun accept_flow_visitor(v) + do + var after_expr = v.visit_expr(self.n_expr) + + v.current_flow_context = after_expr.when_true + v.enter_visit(self.n_then) + var after_then = v.current_flow_context + + v.current_flow_context = after_expr.when_false + v.enter_visit(self.n_else) + var after_else = v.current_flow_context + + v.make_merge_flow(after_then, after_else) + end +end + +redef class AIfexprExpr + redef fun accept_flow_visitor(v) + do + var after_expr = v.visit_expr(self.n_expr) + + v.current_flow_context = after_expr.when_true + v.enter_visit(self.n_then) + var after_then = v.current_flow_context + + v.current_flow_context = after_expr.when_false + v.enter_visit(self.n_else) + var after_else = v.current_flow_context + + v.make_merge_flow(after_then, after_else) + end +end + +redef class AWhileExpr + redef fun accept_flow_visitor(v) + do + var before_loop = v.make_sub_flow + + var after_expr = v.visit_expr(self.n_expr) + + v.current_flow_context = after_expr.when_true + v.enter_visit(self.n_block) + var after_block = v.current_flow_context + + before_loop.add_loop(after_block) + v.merge_continues_to(after_block, self.escapemark) + + v.current_flow_context = after_expr.when_false + v.merge_breaks(self.escapemark) + end +end + +redef class ALoopExpr + redef fun accept_flow_visitor(v) + do + var before_loop = v.make_sub_flow + + v.enter_visit(self.n_block) + + var after_block = v.current_flow_context + + before_loop.add_loop(after_block) + v.merge_continues_to(after_block, self.escapemark) + + v.make_unreachable_flow + v.merge_breaks(self.escapemark) + end +end + +redef class AForExpr + redef fun accept_flow_visitor(v) + do + v.enter_visit(self.n_expr) + + var before_loop = v.make_sub_flow + + v.enter_visit(self.n_block) + + var after_block = v.current_flow_context + + before_loop.add_loop(after_block) + v.merge_continues_to(after_block, self.escapemark) + + v.make_merge_flow(v.current_flow_context, before_loop) + v.merge_breaks(self.escapemark) + end +end + +redef class AAssertExpr + redef fun accept_flow_visitor(v) + do + v.enter_visit(self.n_expr) + var after_expr = v.current_flow_context + + v.current_flow_context = after_expr.when_false + v.enter_visit(n_else) + # the after context of n_else is a dead end, so we do not care + + v.current_flow_context = after_expr.when_true + end +end + +redef class AOrExpr + redef fun accept_flow_visitor(v) + do + var after_expr = v.visit_expr(self.n_expr) + + v.current_flow_context = after_expr.when_false + var after_expr2 = v.visit_expr(self.n_expr2) + + v.make_true_false_flow(v.make_merge_flow(after_expr.when_true, after_expr2.when_true), after_expr2.when_false) + end +end + +redef class AAndExpr + redef fun accept_flow_visitor(v) + do + var after_expr = v.visit_expr(self.n_expr) + + v.current_flow_context = after_expr.when_true + var after_expr2 = v.visit_expr(self.n_expr2) + + var merge_false = v.make_merge_flow(after_expr.when_false, after_expr2.when_false) + merge_false.name = "AND FALSE" + + v.make_true_false_flow(after_expr2.when_true, merge_false) + end +end + +redef class ANotExpr + redef fun accept_flow_visitor(v) + do + var after_expr = v.visit_expr(self.n_expr) + + v.make_true_false_flow(after_expr.when_false, after_expr.when_true) + end +end + +redef class AOrElseExpr + redef fun accept_flow_visitor(v) + do + super + end +end + +redef class AEqExpr + redef fun accept_flow_visitor(v) + do + super + v.make_sub_true_false_flow + end +end + + +redef class ANeExpr + redef fun accept_flow_visitor(v) + do + super + v.make_sub_true_false_flow + end +end + +redef class AClosureCallExpr + redef fun accept_flow_visitor(v) + do + super + # FIXME: break closure call? + # v.make_unreachable_flow + end +end + +redef class AClosureDef + redef fun accept_flow_visitor(v) + do + var before_loop = v.make_sub_flow + + v.enter_visit(self.n_expr) + + var after_block = v.current_flow_context + before_loop.add_loop(after_block) + + v.make_merge_flow(v.current_flow_context, before_loop) + end +end + +redef class AIsaExpr + redef fun accept_flow_visitor(v) + do + super + v.make_sub_true_false_flow + end +end diff --git a/src/literal.nit b/src/literal.nit new file mode 100644 index 0000000..bdea381 --- /dev/null +++ b/src/literal.nit @@ -0,0 +1,146 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Parsing of literal values in the abstract syntax tree. +module literal + +import parser +import toolcontext + +redef class AModule + # Visit the module to compute the real value of the literal-related node of the AST. + # Warnings and errors are displayed on the toolcontext. + fun do_literal(toolcontext: ToolContext) + do + var v = new LiteralVisitor(toolcontext) + v.enter_visit(self) + end +end + +private class LiteralVisitor + super Visitor + + var toolcontext: ToolContext + + init(toolcontext: ToolContext) + do + self.toolcontext = toolcontext + end + + redef fun visit(n) + do + if n != null then + n.accept_literal(self) + n.visit_all(self) + end + end +end + +redef class ANode + private fun accept_literal(v: LiteralVisitor) do end +end + +redef class AIntExpr + # The value of the literal int once computed. + var value: nullable Int + redef fun accept_literal(v) + do + self.value = self.n_number.text.to_i + end +end + +redef class AFloatExpr + # The value of the literal float once computed. + var value: nullable Float + redef fun accept_literal(v) + do + # FIXME: no method to_f on string so just go ugly + var parts = self.n_float.text.split_with(".") + self.value = parts.first.to_i.to_f + end +end + +redef class ACharExpr + # The value of the literal char once computed. + var value: nullable Char + redef fun accept_literal(v) + do + var txt = self.n_char.text.unescape_nit + if txt.length != 3 then + v.toolcontext.error(self.hot_location, "Invalid character literal {txt}") + return + end + self.value = txt[1] + end +end + +redef class AStringFormExpr + # The value of the literal string once computed. + var value: nullable String + redef fun accept_literal(v) + do + var txt + if self isa AStringExpr then + txt = self.n_string.text + else if self isa AStartStringExpr then + txt = self.n_string.text + else if self isa AMidStringExpr then + txt = self.n_string.text + else if self isa AEndStringExpr then + txt = self.n_string.text + else abort + self.value = txt.substring(1, txt.length-2).unescape_nit + end +end + +redef class String + # Return a string where Nit escape sequences are transformed. + # + # Example: + # var s = "\\n" + # print s.length # -> 2 + # var u = s.unescape_nit + # print s.length # -> 1 + # print s[0].ascii # -> 10 (the ASCII value of the "new line" character) + fun unescape_nit: String + do + var res = new Buffer.with_capacity(self.length) + var was_slash = false + for c in self do + if not was_slash then + if c == '\\' then + was_slash = true + else + res.add(c) + end + continue + end + was_slash = false + if c == 'n' then + res.add('\n') + else if c == 'r' then + res.add('\r') + else if c == 't' then + res.add('\t') + else if c == '0' then + res.add('\0') + else + res.add(c) + end + end + return res.to_s + end +end diff --git a/src/local_var_init.nit b/src/local_var_init.nit new file mode 100644 index 0000000..0ef4b4a --- /dev/null +++ b/src/local_var_init.nit @@ -0,0 +1,145 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Verify that local variables are initialized before their usage +# Require that the scope and the flow analaysis are already performed +module local_var_init + +import scope +import flow + +redef class APropdef + # Entry point of the whole local variable initialization verifier + fun do_local_var_init(toolcontext: ToolContext) + do + var v = new LocalVarInitVisitor(toolcontext) + v.enter_visit(self) + end +end + +private class LocalVarInitVisitor + super Visitor + + var toolcontext: ToolContext + + init(toolcontext: ToolContext) + do + self.toolcontext = toolcontext + end + + # Local variables that are possibily unset (ie local variable without an initial value) + var maybe_unset_vars: Set[Variable] = new HashSet[Variable] + + fun mark_is_unset(node: AExpr, variable: nullable Variable) + do + assert variable != null + self.maybe_unset_vars.add(variable) + end + + fun mark_is_set(node: AExpr, variable: nullable Variable) + do + assert variable != null + if not maybe_unset_vars.has(variable) then return + + var flow = node.after_flow_context.as(not null) + flow.set_vars.add(variable) + end + + fun check_is_set(node: AExpr, variable: nullable Variable) + do + assert variable != null + if not maybe_unset_vars.has(variable) then return + + var flow = node.after_flow_context.as(not null) + if not flow.is_variable_set(variable) then + self.toolcontext.error(node.hot_location, "Error: variable '{variable}' is possibly unset.") + # Remove the variable to avoid repetting errors + self.maybe_unset_vars.remove(variable) + end + end + + redef fun visit(n) + do + if n != null then n.accept_local_var_visitor(self) + end +end + +redef class FlowContext + private var set_vars: Set[Variable] = new HashSet[Variable] + + private fun is_variable_set(variable: Variable): Bool + do + if self.set_vars.has(variable) then return true + var previous = self.previous + if previous.length == 0 then return false + if previous.length == 1 then return previous.first.is_variable_set(variable) + for p in self.previous do + if not p.is_variable_set(variable) then + return false + end + end + # Cache the result + self.set_vars.add(variable) + return true + end +end + +redef class ANode + private fun accept_local_var_visitor(v: LocalVarInitVisitor) do self.visit_all(v) +end + +redef class AVardeclExpr + redef fun accept_local_var_visitor(v) + do + super + # The variable is unset only if there is no initial value. + + # Note: loops in inital value are not a problem + # Example: + # + # var foo = foo + 1 #-> Error during typing: "self.foo" unknown + # + # var foo + # foo = foo + 1 #-> Error here because 'foo' is possibly unset + if self.n_expr == null then + v.mark_is_unset(self, self.variable) + end + end +end + +redef class AVarExpr + redef fun accept_local_var_visitor(v) + do + super + v.check_is_set(self, self.variable) + end +end + +redef class AVarAssignExpr + redef fun accept_local_var_visitor(v) + do + super + v.mark_is_set(self, self.variable) + end +end + +redef class AVarReassignExpr + redef fun accept_local_var_visitor(v) + do + super + v.check_is_set(self, self.variable) + end +end diff --git a/src/model/model.nit b/src/model/model.nit new file mode 100644 index 0000000..87b6a15 --- /dev/null +++ b/src/model/model.nit @@ -0,0 +1,1454 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Object model of the Nit language +# +# This module define the entities of the Nit meta-model like modules, +# classes, types and properties +# +# It also provide an API to build and query models. +# +# All model classes starts with the M letter (MModule, MClass, etc.) +# +# TODO: better doc +# +# TODO: liearization, closures, extern stuff +# FIXME: better handling of the types +module model + +import poset +import location +import model_base + +redef class Model + # All known classes + var mclasses: Array[MClass] = new Array[MClass] + + # All known properties + var mproperties: Array[MProperty] = new Array[MProperty] + + # Hierarchy of class definition. + # + # Each classdef is associated with its super-classdefs in regard to + # its module of definition. + var mclassdef_hierarchy: POSet[MClassDef] = new POSet[MClassDef] + + # Class-type hierarchy restricted to the introduction. + # + # The idea is that what is true on introduction is always true whatever + # the module considered. + # Therefore, this hierarchy is used for a fast positive subtype check. + # + # This poset will evolve in a monotonous way: + # * Two non connected nodes will remain unconnected + # * New nodes can appear with new edges + private var intro_mtype_specialization_hierarchy: POSet[MClassType] = new POSet[MClassType] + + # Global overlapped class-type hierarchy. + # The hierarchy when all modules are combined. + # Therefore, this hierarchy is used for a fast negative subtype check. + # + # This poset will evolve in an anarchic way. Loops can even be created. + # + # FIXME decide what to do on loops + private var full_mtype_specialization_hierarchy: POSet[MClassType] = new POSet[MClassType] + + # Collections of classes grouped by their short name + private var mclasses_by_name: MultiHashMap[String, MClass] = new MultiHashMap[String, MClass] + + # Return all class named `name'. + # + # If such a class does not exist, null is returned + # (instead of an empty array) + # + # Visibility or modules are not considered + fun get_mclasses_by_name(name: String): nullable Array[MClass] + do + if mclasses_by_name.has_key(name) then + return mclasses_by_name[name] + else + return null + end + end + + # Collections of properties grouped by their short name + private var mproperties_by_name: MultiHashMap[String, MProperty] = new MultiHashMap[String, MProperty] + + # Return all properties named `name'. + # + # If such a property does not exist, null is returned + # (instead of an empty array) + # + # Visibility or modules are not considered + fun get_mproperties_by_name(name: String): nullable Array[MProperty] + do + if not mproperties_by_name.has_key(name) then + return null + else + return mproperties_by_name[name] + end + end + + # The only null type + var null_type: MNullType = new MNullType(self) +end + +redef class MModule + # All the classes introduced in the module + var intro_mclasses: Array[MClass] = new Array[MClass] + + # All the class definitions of the module + # (introduction and refinement) + var mclassdefs: Array[MClassDef] = new Array[MClassDef] + + # Does the current module has a given class `mclass'? + # Return true if the mmodule introduces, refines or imports a class. + # Visibility is not considered. + fun has_mclass(mclass: MClass): Bool + do + return self.in_importation <= mclass.intro_mmodule + end + + # Full hierarchy of introduced ans imported classes. + # + # Create a new hierarchy got by flattening the classes for the module + # and its imported modules. + # Visibility is not considered. + # + # Note: this function is expensive and is usually used for the main + # module of a program only. Do not use it to do you own subtype + # functions. + fun flatten_mclass_hierarchy: POSet[MClass] + do + var res = self.flatten_mclass_hierarchy_cache + if res != null then return res + res = new POSet[MClass] + for m in self.in_importation.greaters do + for cd in m.mclassdefs do + var c = cd.mclass + for s in cd.supertypes do + res.add_edge(c, s.mclass) + end + end + end + self.flatten_mclass_hierarchy_cache = res + return res + end + + private var flatten_mclass_hierarchy_cache: nullable POSet[MClass] = null +end + +# A named class +# +# MClass are global to the model; it means that a MClass is not bound to a +# specific `MModule`. +# +# This characteristic helps the reasoning about classes in a program since a +# single MClass object always denote the same class. +# However, because a MClass is global, it does not really have properties nor +# belong to a hierarchy since the property and the +# hierarchy of a class depends of a module. +class MClass + # The module that introduce the class + # While classes are not bound to a specific module, + # the introducing module is used for naming an visibility + var intro_mmodule: MModule + + # The short name of the class + # In Nit, the name of a class cannot evolve in refinements + var name: String + + # The canonical name of the class + # Example: "owner::module::MyClass" + fun full_name: String + do + return "{self.intro_mmodule.full_name}::{name}" + end + + # The number of generic formal parameters + # 0 if the class is not generic + var arity: Int + + # The kind of the class (interface, abstract class, etc.) + # In Nit, the kind of a class cannot evolve in refinements + var kind: MClassKind + + # The visibility of the class + # In Nit, the visibility of a class cannot evolve in refinements + var visibility: MVisibility + + init(intro_mmodule: MModule, name: String, arity: Int, kind: MClassKind, visibility: MVisibility) + do + self.intro_mmodule = intro_mmodule + self.name = name + self.arity = arity + self.kind = kind + self.visibility = visibility + intro_mmodule.intro_mclasses.add(self) + var model = intro_mmodule.model + model.mclasses_by_name.add_one(name, self) + model.mclasses.add(self) + + # Create the formal parameter types + if arity > 0 then + var mparametertypes = new Array[MParameterType] + for i in [0..arity[ do + var mparametertype = new MParameterType(self, i) + mparametertypes.add(mparametertype) + end + var mclass_type = new MGenericType(self, mparametertypes) + self.mclass_type = mclass_type + self.get_mtype_cache.add(mclass_type) + else + self.mclass_type = new MClassType(self) + end + end + + # All class definitions (introduction and refinements) + var mclassdefs: Array[MClassDef] = new Array[MClassDef] + + # Alias for `name' + redef fun to_s do return self.name + + # The definition that introduced the class + # Warning: the introduction is the first `MClassDef' object associated + # to self. If self is just created without having any associated + # definition, this method will abort + private fun intro: MClassDef + do + assert has_a_first_definition: not mclassdefs.is_empty + return mclassdefs.first + end + + # The principal static type of the class. + # + # For non-generic class, mclass_type is the only MClassType based + # on self. + # + # For a generic class, the arguments are the formal parameters. + # i.e.: for the class `Array[E:Object]', the mtype is Array[E]. + # If you want `Array[Object]' the see `MClassDef::bound_mtype' + # + # For generic classes, the mclass_type is also the way to get a formal + # generic parameter type. + # + # To get other types based on a generic class, see `get_mtype'. + # + # ENSURE: mclass_type.mclass == self + var mclass_type: MClassType + + # Return a generic type based on the class + # Is the class is not generic, then the result is `mclass_type' + # + # REQUIRE: type_arguments.length == self.arity + fun get_mtype(mtype_arguments: Array[MType]): MClassType + do + assert mtype_arguments.length == self.arity + if self.arity == 0 then return self.mclass_type + for t in self.get_mtype_cache do + if t.arguments == mtype_arguments then + return t + end + end + var res = new MGenericType(self, mtype_arguments) + self.get_mtype_cache.add res + return res + end + + private var get_mtype_cache: Array[MGenericType] = new Array[MGenericType] +end + + +# A definition (an introduction or a refinement) of a class in a module +# +# A MClassDef is associated with an explicit (or almost) definition of a +# class. Unlike MClass, a MClassDef is a local definition that belong to +# a specific module +class MClassDef + # The module where the definition is + var mmodule: MModule + + # The associated MClass + var mclass: MClass + + # The bounded type associated to the mclassdef + # + # For a non-generic class, `bound_mtype' and `mclass.mclass_type' + # are the same type. + # + # Example: + # For the classdef Array[E: Object], the bound_mtype is Array[Object]. + # If you want Array[E], then see `mclass.mclass_type' + # + # ENSURE: bound_mtype.mclass = self.mclass + var bound_mtype: MClassType + + # Name of each formal generic parameter (in order of declaration) + var parameter_names: Array[String] + + # The origin of the definition + var location: Location + + # Internal name combining the module and the class + # Example: "mymodule#MyClass" + redef fun to_s do return "{mmodule}#{mclass}" + + init(mmodule: MModule, bound_mtype: MClassType, location: Location, parameter_names: Array[String]) + do + assert bound_mtype.mclass.arity == parameter_names.length + self.bound_mtype = bound_mtype + self.mmodule = mmodule + self.mclass = bound_mtype.mclass + self.location = location + mmodule.mclassdefs.add(self) + mclass.mclassdefs.add(self) + self.parameter_names = parameter_names + end + + # All declared super-types + # FIXME: quite ugly but not better idea yet + var supertypes: Array[MClassType] = new Array[MClassType] + + # Register the super-types for the class (ie "super SomeType") + # This function can only invoked once by class + fun set_supertypes(supertypes: Array[MClassType]) + do + assert unique_invocation: self.in_hierarchy == null + var mmodule = self.mmodule + var model = mmodule.model + var res = model.mclassdef_hierarchy.add_node(self) + self.in_hierarchy = res + var mtype = self.bound_mtype + + for supertype in supertypes do + self.supertypes.add(supertype) + + # Register in full_type_specialization_hierarchy + model.full_mtype_specialization_hierarchy.add_edge(mtype, supertype) + # Register in intro_type_specialization_hierarchy + if mclass.intro_mmodule == mmodule and supertype.mclass.intro_mmodule == mmodule then + model.intro_mtype_specialization_hierarchy.add_edge(mtype, supertype) + end + end + + for mclassdef in mtype.collect_mclassdefs(mmodule) do + res.poset.add_edge(self, mclassdef) + end + end + + # The view of the class definition in `mclassdef_hierarchy' + var in_hierarchy: nullable POSetElement[MClassDef] = null + + # Is the definition the one that introduced `mclass`? + fun is_intro: Bool do return mclass.intro == self + + # All properties introduced by the classdef + var intro_mproperties: Array[MProperty] = new Array[MProperty] + + # All property definitions in the class (introductions and redefinitions) + var mpropdefs: Array[MPropDef] = new Array[MPropDef] +end + +# A global static type +# +# MType are global to the model; it means that a MType is not bound to a +# specific `MModule`. +# This characteristic helps the reasoning about static types in a program +# since a single MType object always denote the same type. +# +# However, because a MType is global, it does not really have properties +# nor have subtypes to a hierarchy since the property and the class hierarchy +# depends of a module. +# Moreover, virtual types an formal generic parameter types also depends on +# a receiver to have sense. +# +# Therefore, most method of the types require a module and an anchor. +# The module is used to know what are the classes and the specialization +# links. +# The anchor is used to know what is the bound of the virtual types and formal +# generic parameter types. +# +# MType are not directly usable to get properties. See the `anchor_to' method +# and the `MClassType' class. +# +# FIXME: the order of the parameters is not the best. We mus pick on from: +# * foo(mmodule, anchor, othertype) +# * foo(othertype, anchor, mmodule) +# * foo(anchor, mmodule, othertype) +# * foo(othertype, mmodule, anchor) +# +# FIXME: Add a 'is_valid_anchor' to improve imputability. +# Currently, anchors are used "as it" without check thus if the caller gives a +# bad anchor, then the method will likely crash (abort) in a bad case +# +# FIXME: maybe allways add an anchor with a nullable type (as in is_subtype) +abstract class MType + # Return true if `self' is an subtype of `sup'. + # The typing is done using the standard typing policy of Nit. + # + # REQUIRE: anchor == null implies not self.need_anchor and not sup.need_anchor + fun is_subtype(mmodule: MModule, anchor: nullable MClassType, sup: MType): Bool + do + var sub = self + if anchor == null then + assert not sub.need_anchor + assert not sup.need_anchor + end + # First, resolve the types + if sub isa MParameterType or sub isa MVirtualType then + assert anchor != null + sub = sub.resolve_for(anchor, anchor, mmodule, false) + end + if sup isa MParameterType or sup isa MVirtualType then + assert anchor != null + sup = sup.resolve_for(anchor, anchor, mmodule, false) + end + + if sup isa MParameterType or sup isa MVirtualType or sup isa MNullType then + return sub == sup + end + if sub isa MParameterType or sub isa MVirtualType then + assert anchor != null + sub = sub.anchor_to(mmodule, anchor) + end + if sup isa MNullableType then + if sub isa MNullType then + return true + else if sub isa MNullableType then + return sub.mtype.is_subtype(mmodule, anchor, sup.mtype) + else if sub isa MClassType then + return sub.is_subtype(mmodule, anchor, sup.mtype) + else + abort + end + end + + assert sup isa MClassType # It is the only remaining type + if sub isa MNullableType or sub isa MNullType then + return false + end + + assert sub isa MClassType # It is the only remaining type + if anchor == null then anchor = sub # UGLY: any anchor will work + var resolved_sub = sub.anchor_to(mmodule, anchor) + var res = resolved_sub.collect_mclasses(mmodule).has(sup.mclass) + if res == false then return false + if not sup isa MGenericType then return true + var sub2 = sub.supertype_to(mmodule, anchor, sup.mclass) + assert sub2.mclass == sup.mclass + assert sub2 isa MGenericType + for i in [0..sup.mclass.arity[ do + var sub_arg = sub2.arguments[i] + var sup_arg = sup.arguments[i] + res = sub_arg.is_subtype(mmodule, anchor, sup_arg) + if res == false then return false + end + return true + end + + # The base class type on which self is based + # + # This base type is used to get property (an internally to perform + # unsafe type comparison). + # + # Beware: some types (like null) are not based on a class thus this + # method will crash + # + # Basically, this function transform the virtual types and parameter + # types to their bounds. + # + # Example + # class G[T: A] + # type U: X + # end + # class H + # super G[C] + # redef type U: Y + # end + # Map[T,U] anchor_to H #-> Map[C,Y] + # + # Explanation of the example: + # In H, T is set to C, because "H super G[C]", and U is bound to Y, + # because "redef type U: Y". Therefore, Map[T, U] is bound to + # Map[C, Y] + # + # ENSURE: not self.need_anchor implies return == self + # ENSURE: not return.need_anchor + fun anchor_to(mmodule: MModule, anchor: MClassType): MType + do + if not need_anchor then return self + assert not anchor.need_anchor + # Just resolve to the anchor and clear all the virtual types + var res = self.resolve_for(anchor, anchor, mmodule, true) + assert not res.need_anchor + return res + end + + # Does `self' contain a virtual type or a formal generic parameter type? + # In order to remove those types, you usually want to use `anchor_to'. + fun need_anchor: Bool do return true + + # Return the supertype when adapted to a class. + # + # In Nit, for each super-class of a type, there is a equivalent super-type. + # + # Example: + # class G[T, U] + # class H[V] super G[V, Bool] + # H[Int] supertype_to G #-> G[Int, Bool] + # + # REQUIRE: `super_mclass' is a super-class of `self' + # ENSURE: return.mclass = mclass + fun supertype_to(mmodule: MModule, anchor: MClassType, super_mclass: MClass): MClassType + do + if super_mclass.arity == 0 then return super_mclass.mclass_type + if self isa MClassType and self.mclass == super_mclass then return self + var resolved_self = self.anchor_to(mmodule, anchor) + var supertypes = resolved_self.collect_mtypes(mmodule) + for supertype in supertypes do + if supertype.mclass == super_mclass then + # FIXME: Here, we stop on the first goal. Should we check others and detect inconsistencies? + return supertype.resolve_for(self, anchor, mmodule, false) + end + end + abort + end + + # Replace formals generic types in self with resolved values in `mtype' + # If `cleanup_virtual' is true, then virtual types are also replaced + # with their bounds + # + # This function returns self if `need_anchor' is false. + # + # Example: + # class G[E] + # class H[F] super G[F] + # Array[E] resolve_for H[Int] #-> Array[Int] + # + # Explanation of the example: + # * Array[E].need_anchor is true because there is a formal generic + # parameter type E + # * E makes sense for H[Int] because E is a formal parameter of G + # and H specialize G + # * Since "H[F] super G[F]", E is in fact F for H + # * More specifically, in H[Int], E is Int + # * So, in H[Int], Array[E] is Array[Int] + # + # This function is mainly used to inherit a signature. + # Because, unlike `anchor_type', we do not want a full resolution of + # a type but only an adapted version of it. + # + # Example: + # class A[E] + # foo(e:E):E + # end + # class B super A[Int] end + # + # The signature on foo is (e: E): E + # If we resolve the signature for B, we get (e:Int):Int + # + # TODO: Explain the cleanup_virtual + # + # FIXME: the parameter `cleanup_virtual' is just a bad idea, but having + # two function instead of one seems also to be a bad idea. + # + # ENSURE: not self.need_anchor implies return == self + fun resolve_for(mtype: MType, anchor: MClassType, mmodule: MModule, cleanup_virtual: Bool): MType is abstract + + # Return the nullable version of the type + # If the type is already nullable then self is returned + # + # FIXME: DO NOT WORK YET + fun as_nullable: MType + do + var res = self.as_nullable_cache + if res != null then return res + res = new MNullableType(self) + self.as_nullable_cache = res + return res + end + + private var as_nullable_cache: nullable MType = null + + # Compute all the classdefs inherited/imported. + # The returned set contains: + # * the class definitions from `mmodule` and its imported modules + # * the class definitions of this type and its super-types + # + # This function is used mainly internally. + # + # REQUIRE: not self.need_anchor + fun collect_mclassdefs(mmodule: MModule): Set[MClassDef] is abstract + + # Compute all the super-classes. + # This function is used mainly internally. + # + # REQUIRE: not self.need_anchor + fun collect_mclasses(mmodule: MModule): Set[MClass] is abstract + + # Compute all the declared super-types. + # Super-types are returned as declared in the classdefs (verbatim). + # This function is used mainly internally. + # + # REQUIRE: not self.need_anchor + fun collect_mtypes(mmodule: MModule): Set[MClassType] is abstract + + # Is the property in self for a given module + # This method does not filter visibility or whatever + # + # REQUIRE: not self.need_anchor + fun has_mproperty(mmodule: MModule, mproperty: MProperty): Bool + do + assert not self.need_anchor + return self.collect_mclassdefs(mmodule).has(mproperty.intro_mclassdef) + end +end + +# A type based on a class. +# +# MClassType have properties (see `has_property'). +class MClassType + super MType + + # The associated class + var mclass: MClass + + private init(mclass: MClass) + do + self.mclass = mclass + end + + redef fun to_s do return mclass.to_s + + redef fun need_anchor do return false + + redef fun anchor_to(mmodule: MModule, anchor: MClassType): MClassType + do + return super.as(MClassType) + end + + redef fun resolve_for(mtype: MType, anchor: MClassType, mmodule: MModule, cleanup_virtual: Bool): MClassType do return self + + redef fun collect_mclassdefs(mmodule) + do + assert not self.need_anchor + if not collect_mclassdefs_cache.has_key(mmodule) then + self.collect_things(mmodule) + end + return collect_mclassdefs_cache[mmodule] + end + + redef fun collect_mclasses(mmodule) + do + assert not self.need_anchor + if not collect_mclasses_cache.has_key(mmodule) then + self.collect_things(mmodule) + end + return collect_mclasses_cache[mmodule] + end + + redef fun collect_mtypes(mmodule) + do + assert not self.need_anchor + if not collect_mtypes_cache.has_key(mmodule) then + self.collect_things(mmodule) + end + return collect_mtypes_cache[mmodule] + end + + # common implementation for `collect_mclassdefs', `collect_mclasses', and `collect_mtypes'. + private fun collect_things(mmodule: MModule) + do + var res = new HashSet[MClassDef] + var seen = new HashSet[MClass] + var types = new HashSet[MClassType] + seen.add(self.mclass) + var todo = [self.mclass] + while not todo.is_empty do + var mclass = todo.pop + #print "process {mclass}" + for mclassdef in mclass.mclassdefs do + if not mmodule.in_importation <= mclassdef.mmodule then continue + #print " process {mclassdef}" + res.add(mclassdef) + for supertype in mclassdef.supertypes do + types.add(supertype) + var superclass = supertype.mclass + if seen.has(superclass) then continue + #print " add {superclass}" + seen.add(superclass) + todo.add(superclass) + end + end + end + collect_mclassdefs_cache[mmodule] = res + collect_mclasses_cache[mmodule] = seen + collect_mtypes_cache[mmodule] = types + end + + private var collect_mclassdefs_cache: HashMap[MModule, Set[MClassDef]] = new HashMap[MModule, Set[MClassDef]] + private var collect_mclasses_cache: HashMap[MModule, Set[MClass]] = new HashMap[MModule, Set[MClass]] + private var collect_mtypes_cache: HashMap[MModule, Set[MClassType]] = new HashMap[MModule, Set[MClassType]] + +end + +# A type based on a generic class. +# A generic type a just a class with additional formal generic arguments. +class MGenericType + super MClassType + + private init(mclass: MClass, arguments: Array[MType]) + do + super(mclass) + assert self.mclass.arity == arguments.length + self.arguments = arguments + + self.need_anchor = false + for t in arguments do + if t.need_anchor then + self.need_anchor = true + break + end + end + end + + # The formal arguments of the type + # ENSURE: return.length == self.mclass.arity + var arguments: Array[MType] + + # Recursively print the type of the arguments within brackets. + # Example: "Map[String,List[Int]]" + redef fun to_s + do + return "{mclass}[{arguments.join(",")}]" + end + + redef var need_anchor: Bool + + redef fun resolve_for(mtype, anchor, mmodule, cleanup_virtual) + do + if not need_anchor then return self + var types = new Array[MType] + for t in arguments do + types.add(t.resolve_for(mtype, anchor, mmodule, cleanup_virtual)) + end + return mclass.get_mtype(types) + end +end + +# A virtual formal type. +class MVirtualType + super MType + + # The property associated with the type. + # Its the definitions of this property that determine the bound or the virtual type. + var mproperty: MProperty + + # Lookup the bound for a given resolved_receiver + # The result may be a other virtual type (or a parameter type) + # + # The result is returned exactly as declared in the "type" property (verbatim). + # + # In case of conflict, the method aborts. + fun lookup_bound(mmodule: MModule, resolved_receiver: MType): MType + do + assert not resolved_receiver.need_anchor + var props = self.mproperty.lookup_definitions(mmodule, resolved_receiver) + if props.is_empty then + abort + else if props.length == 1 then + return props.first.as(MVirtualTypeDef).bound.as(not null) + end + var types = new ArraySet[MType] + for p in props do + types.add(p.as(MVirtualTypeDef).bound.as(not null)) + end + if types.length == 1 then + return types.first + end + abort + end + + redef fun resolve_for(mtype, anchor, mmodule, cleanup_virtual) + do + if not cleanup_virtual then return self + # self is a virtual type declared (or inherited) in mtype + # The point of the function it to get the bound of the virtual type that make sense for mtype + # But because mtype is maybe a virtual/formal type, we need to get a real receiver first + #print "{class_name}: {self}/{mtype}/{anchor}?" + var resolved_reciever = mtype.resolve_for(anchor, anchor, mmodule, true) + # Now, we can get the bound + var verbatim_bound = lookup_bound(mmodule, resolved_reciever) + # The bound is exactly as declared in the "type" property, so we must resolve it again + var res = verbatim_bound.resolve_for(mtype, anchor, mmodule, true) + #print "{class_name}: {self}/{mtype}/{anchor} -> {self}/{resolved_reciever}/{anchor} -> {verbatim_bound}/{mtype}/{anchor} -> {res}" + return res + end + + redef fun to_s do return self.mproperty.to_s + + init(mproperty: MProperty) + do + self.mproperty = mproperty + end +end + +# The type associated the a formal parameter generic type of a class +# +# Each parameter type is associated to a specific class. +# It's mean that all refinements of a same class "share" the parameter type, +# but that a generic subclass has its on parameter types. +# +# However, in the sense of the meta-model, the a parameter type of a class is +# a valid types in a subclass. The "in the sense of the meta-model" is +# important because, in the Nit language, the programmer cannot refers +# directly to the parameter types of the super-classes. +# +# Example: +# class A[E] +# fun e: E is abstract +# end +# class B[F] +# super A[Array[F]] +# end +# In the class definition B[F], `F' is a valid type but `E' is not. +# However, `self.e' is a valid method call, and the signature of `e' is +# declared `e: E'. +# +# Note that parameter types are shared among class refinements. +# Therefore parameter only have an internal name (see `to_s' for details). +# TODO: Add a 'name_for' to get better messages. +class MParameterType + super MType + + # The generic class where the parameter belong + var mclass: MClass + + # The position of the parameter (0 for the first parameter) + # FIXME: is `position' a better name? + var rank: Int + + # Internal name of the parameter type + # Names of parameter types changes in each class definition + # Therefore, this method return an internal name. + # Example: return "G#1" for the second parameter of the class G + # FIXME: add a way to get the real name in a classdef + redef fun to_s do return "{mclass}#{rank}" + + # Resolve the bound for a given resolved_receiver + # The result may be a other virtual type (or a parameter type) + fun lookup_bound(mmodule: MModule, resolved_receiver: MType): MType + do + assert not resolved_receiver.need_anchor + var goalclass = self.mclass + var supertypes = resolved_receiver.collect_mtypes(mmodule) + for t in supertypes do + if t.mclass == goalclass then + # Yeah! c specialize goalclass with a "super `t'". So the question is what is the argument of f + # FIXME: Here, we stop on the first goal. Should we check others and detect inconsistencies? + assert t isa MGenericType + var res = t.arguments[self.rank] + return res + end + end + abort + end + + redef fun resolve_for(mtype, anchor, mmodule, cleanup_virtual) + do + #print "{class_name}: {self}/{mtype}/{anchor}?" + + if mtype isa MGenericType and mtype.mclass == self.mclass then + return mtype.arguments[self.rank] + end + + # self is a parameter type of mtype (or of a super-class of mtype) + # The point of the function it to get the bound of the virtual type that make sense for mtype + # But because mtype is maybe a virtual/formal type, we need to get a real receiver first + # FIXME: What happend here is far from clear. Thus this part must be validated and clarified + var resolved_receiver = mtype.resolve_for(anchor.mclass.mclass_type, anchor, mmodule, true) + if resolved_receiver isa MNullableType then resolved_receiver = resolved_receiver.mtype + if resolved_receiver isa MParameterType then + assert resolved_receiver.mclass == anchor.mclass + resolved_receiver = anchor.as(MGenericType).arguments[resolved_receiver.rank] + if resolved_receiver isa MNullableType then resolved_receiver = resolved_receiver.mtype + end + assert resolved_receiver isa MClassType else print "{class_name}: {self}/{mtype}/{anchor}? {resolved_receiver}" + + # Eh! The parameter is in the current class. + # So we return the corresponding argument, no mater what! + if resolved_receiver.mclass == self.mclass then + assert resolved_receiver isa MGenericType + var res = resolved_receiver.arguments[self.rank] + #print "{class_name}: {self}/{mtype}/{anchor} -> direct {res}" + return res + end + + resolved_receiver = resolved_receiver.resolve_for(anchor, anchor, mmodule, false) + # Now, we can get the bound + var verbatim_bound = lookup_bound(mmodule, resolved_receiver) + # The bound is exactly as declared in the "type" property, so we must resolve it again + var res = verbatim_bound.resolve_for(mtype, anchor, mmodule, cleanup_virtual) + + #print "{class_name}: {self}/{mtype}/{anchor} -> indirect {res}" + + return res + end + + init(mclass: MClass, rank: Int) + do + self.mclass = mclass + self.rank = rank + end +end + +# A type prefixed with "nullable" +# FIXME Stub implementation +class MNullableType + super MType + + # The base type of the nullable type + var mtype: MType + + init(mtype: MType) + do + self.mtype = mtype + end + + redef fun to_s do return "nullable {mtype}" + + redef fun need_anchor do return mtype.need_anchor + redef fun as_nullable do return self + redef fun resolve_for(mtype, anchor, mmodule, cleanup_virtual) + do + var res = self.mtype.resolve_for(mtype, anchor, mmodule, cleanup_virtual) + return res.as_nullable + end + + redef fun collect_mclassdefs(mmodule) + do + assert not self.need_anchor + return self.mtype.collect_mclassdefs(mmodule) + end + + redef fun collect_mclasses(mmodule) + do + assert not self.need_anchor + return self.mtype.collect_mclasses(mmodule) + end + + redef fun collect_mtypes(mmodule) + do + assert not self.need_anchor + return self.mtype.collect_mtypes(mmodule) + end +end + +# The type of the only value null +# +# The is only one null type per model, see `MModel::null_type'. +class MNullType + super MType + var model: Model + protected init(model: Model) + do + self.model = model + end + redef fun to_s do return "null" + redef fun as_nullable do return self + redef fun need_anchor do return false + redef fun resolve_for(mtype, anchor, mmodule, cleanup_virtual) do return self + + redef fun collect_mclassdefs(mmodule) do return new HashSet[MClassDef] + + redef fun collect_mclasses(mmodule) do return new HashSet[MClass] + + redef fun collect_mtypes(mmodule) do return new HashSet[MClassType] +end + +# A signature of a method (or a closure) +class MSignature + super MType + + # The names of each parameter (in order) + var parameter_names: Array[String] + + # The types of each parameter (in order) + var parameter_mtypes: Array[MType] + + # The return type (null for a procedure) + var return_mtype: nullable MType + + # All closures + var mclosures: Array[MClosureDecl] = new Array[MClosureDecl] + + init(parameter_names: Array[String], parameter_mtypes: Array[MType], return_mtype: nullable MType, vararg_rank: Int) + do + self.parameter_names = parameter_names + self.parameter_mtypes = parameter_mtypes + self.return_mtype = return_mtype + self.vararg_rank = vararg_rank + end + + # Is there closures in the signature? + fun with_mclosure: Bool do return not self.mclosures.is_empty + + # The rank of the ellipsis (...) for vararg (starting from 0). + # value is -1 if there is no vararg. + # Example: for "(a: Int, b: Bool..., c: Char)" #-> vararg_rank=1 + var vararg_rank: Int + + # The number or parameters + fun arity: Int do return parameter_mtypes.length + + redef fun to_s + do + var b = new Buffer + if not parameter_names.is_empty then + b.append("(") + for i in [0..parameter_names.length[ do + if i > 0 then b.append(", ") + b.append(parameter_names[i]) + b.append(": ") + b.append(parameter_mtypes[i].to_s) + if i == self.vararg_rank then + b.append("...") + end + end + b.append(")") + end + var ret = self.return_mtype + if ret != null then + b.append(": ") + b.append(ret.to_s) + end + return b.to_s + end + + redef fun resolve_for(mtype: MType, anchor: MClassType, mmodule: MModule, cleanup_virtual: Bool): MSignature + do + var params = new Array[MType] + for t in self.parameter_mtypes do + params.add(t.resolve_for(mtype, anchor, mmodule, cleanup_virtual)) + end + var ret = self.return_mtype + if ret != null then + ret = ret.resolve_for(mtype, anchor, mmodule, cleanup_virtual) + end + var res = new MSignature(self.parameter_names, params, ret, self.vararg_rank) + return res + end +end + +# A closure declaration is a signature +# FIXME Stub implementation +class MClosureDecl + # Is the closure optionnal + var is_optional: Bool + # Has the closure to not continue + var is_break: Bool + # The name of the closure (exluding the !) + var name: String + # The signature of the closure + var msignature: MSignature +end + +# A service (global property) that generalize method, attribute, etc. +# +# MProperty are global to the model; it means that a MProperty is not bound +# to a specific `MModule` nor a specific `MClass`. +# +# A MProperty gather definitions (see `mpropdefs') ; one for the introduction +# and the other in subclasses and in refinements. +# +# A MProperty is used to denotes services in polymorphic way (ie. independent +# of any dynamic type). +# For instance, a call site "x.foo" is associated to a MProperty. +abstract class MProperty + # The associated MPropDef subclass. + # The two specialization hierarchy are symmetric. + type MPROPDEF: MPropDef + + # The classdef that introduce the property + # While a property is not bound to a specific module, or class, + # the introducing mclassdef is used for naming and visibility + var intro_mclassdef: MClassDef + + # The (short) name of the property + var name: String + + # The canonical name of the property + # Example: "owner::my_module::MyClass::my_method" + fun full_name: String + do + return "{self.intro_mclassdef.mmodule.full_name}::{self.intro_mclassdef.mclass.name}::{name}" + end + + # The visibility of the property + var visibility: MVisibility + + init(intro_mclassdef: MClassDef, name: String, visibility: MVisibility) + do + self.intro_mclassdef = intro_mclassdef + self.name = name + self.visibility = visibility + intro_mclassdef.intro_mproperties.add(self) + var model = intro_mclassdef.mmodule.model + model.mproperties_by_name.add_one(name, self) + model.mproperties.add(self) + end + + # All definitions of the property. + # The first is the introduction, + # The other are redefinitions (in refinements and in subclasses) + var mpropdefs: Array[MPROPDEF] = new Array[MPROPDEF] + + # The definition that introduced the property + # Warning: the introduction is the first `MPropDef' object + # associated to self. If self is just created without having any + # associated definition, this method will abort + fun intro: MPROPDEF do return mpropdefs.first + + # Alias for `name' + redef fun to_s do return name + + # Return the most specific property definitions defined or inherited by a type. + # The selection knows that refinement is stronger than specialization; + # however, in case of conflict more than one property are returned. + # If mtype does not know mproperty then an empty array is returned. + # + # If you want the really most specific property, then look at `lookup_first_property` + fun lookup_definitions(mmodule: MModule, mtype: MType): Array[MPROPDEF] + do + assert not mtype.need_anchor + if mtype isa MNullableType then mtype = mtype.mtype + + var cache = self.lookup_definitions_cache[mmodule, mtype] + if cache != null then return cache + + #print "select prop {mproperty} for {mtype} in {self}" + # First, select all candidates + var candidates = new Array[MPROPDEF] + for mpropdef in self.mpropdefs do + # If the definition is not imported by the module, then skip + if not mmodule.in_importation <= mpropdef.mclassdef.mmodule then continue + # If the definition is not inherited by the type, then skip + if not mtype.is_subtype(mmodule, null, mpropdef.mclassdef.bound_mtype) then continue + # Else, we keep it + candidates.add(mpropdef) + end + # Fast track for only one candidate + if candidates.length <= 1 then + self.lookup_definitions_cache[mmodule, mtype] = candidates + return candidates + end + + # Second, filter the most specific ones + var res = new Array[MPROPDEF] + for pd1 in candidates do + var cd1 = pd1.mclassdef + var c1 = cd1.mclass + var keep = true + for pd2 in candidates do + if pd2 == pd1 then continue # do not compare with self! + var cd2 = pd2.mclassdef + var c2 = cd2.mclass + if c2.mclass_type == c1.mclass_type then + if cd2.mmodule.in_importation <= cd1.mmodule then + # cd2 refines cd1; therefore we skip pd1 + keep = false + break + end + else if cd2.bound_mtype.is_subtype(mmodule, null, cd1.bound_mtype) then + # cd2 < cd1; therefore we skip pd1 + keep = false + break + end + end + if keep then + res.add(pd1) + end + end + if res.is_empty then + print "All lost! {candidates.join(", ")}" + # FIXME: should be abort! + end + self.lookup_definitions_cache[mmodule, mtype] = res + return res + end + + private var lookup_definitions_cache: HashMap2[MModule, MType, Array[MPropDef]] = new HashMap2[MModule, MType, Array[MPropDef]] + + # Return the most specific property definitions inherited by a type. + # The selection knows that refinement is stronger than specialization; + # however, in case of conflict more than one property are returned. + # If mtype does not know mproperty then an empty array is returned. + # + # If you want the really most specific property, then look at `lookup_next_definition` + # + # FIXME: Move to MPropDef? + fun lookup_super_definitions(mmodule: MModule, mtype: MType): Array[MPropDef] + do + assert not mtype.need_anchor + if mtype isa MNullableType then mtype = mtype.mtype + + # First, select all candidates + var candidates = new Array[MPropDef] + for mpropdef in self.mpropdefs do + # If the definition is not imported by the module, then skip + if not mmodule.in_importation <= mpropdef.mclassdef.mmodule then continue + # If the definition is not inherited by the type, then skip + if not mtype.is_subtype(mmodule, null, mpropdef.mclassdef.bound_mtype) then continue + # If the definition is defined by the type, then skip (we want the super, so e skip the current) + if mtype == mpropdef.mclassdef.bound_mtype and mmodule == mpropdef.mclassdef.mmodule then continue + # Else, we keep it + candidates.add(mpropdef) + end + # Fast track for only one candidate + if candidates.length <= 1 then return candidates + + # Second, filter the most specific ones + var res = new Array[MPropDef] + for pd1 in candidates do + var cd1 = pd1.mclassdef + var c1 = cd1.mclass + var keep = true + for pd2 in candidates do + if pd2 == pd1 then continue # do not compare with self! + var cd2 = pd2.mclassdef + var c2 = cd2.mclass + if c2.mclass_type == c1.mclass_type then + if cd2.mmodule.in_importation <= cd1.mmodule then + # cd2 refines cd1; therefore we skip pd1 + keep = false + break + end + else if cd2.bound_mtype.is_subtype(mmodule, null, cd1.bound_mtype) then + # cd2 < cd1; therefore we skip pd1 + keep = false + break + end + end + if keep then + res.add(pd1) + end + end + if res.is_empty then + print "All lost! {candidates.join(", ")}" + # FIXME: should be abort! + end + return res + end + + # Return the most specific definition in the linearization of `mtype`. + # If mtype does not know mproperty then null is returned. + # + # If you want to know the next properties in the linearization, + # look at `MPropDef::lookup_next_definition`. + # + # FIXME: NOT YET IMPLEMENTED + # + # REQUIRE: not mtype.need_anchor + fun lookup_first_property(mmodule: MModule, mtype: MType): nullable MPROPDEF + do + assert not mtype.need_anchor + return null + end +end + +# A global method +class MMethod + super MProperty + + redef type MPROPDEF: MMethodDef + + init(intro_mclassdef: MClassDef, name: String, visibility: MVisibility) + do + super + end + + # Is the property a constructor? + # Warning, this property can be inherited by subclasses with or without being a constructor + # therefore, you should use `is_init_for' the verify if the property is a legal constructor for a given class + var is_init: Bool writable = false + + # Is the property a legal constructor for a given class? + # As usual, visibility is not considered. + # FIXME not implemented + fun is_init_for(mclass: MClass): Bool + do + return self.is_init + end +end + +# A global attribute +class MAttribute + super MProperty + + redef type MPROPDEF: MAttributeDef + + init(intro_mclassdef: MClassDef, name: String, visibility: MVisibility) + do + super + end +end + +# A global virtual type +class MVirtualTypeProp + super MProperty + + redef type MPROPDEF: MVirtualTypeDef + + init(intro_mclassdef: MClassDef, name: String, visibility: MVisibility) + do + super + end + + # The formal type associated to the virtual type property + var mvirtualtype: MVirtualType = new MVirtualType(self) +end + +# A definition of a property (local property) +# +# Unlike MProperty, a MPropDef is a local definition that belong to a +# specific class definition (which belong to a specific module) +abstract class MPropDef + + # The associated MProperty subclass. + # the two specialization hierarchy are symmetric + type MPROPERTY: MProperty + + # Self class + type MPROPDEF: MPropDef + + # The origin of the definition + var location: Location + + # The class definition where the property definition is + var mclassdef: MClassDef + + # The associated global property + var mproperty: MPROPERTY + + init(mclassdef: MClassDef, mproperty: MPROPERTY, location: Location) + do + self.mclassdef = mclassdef + self.mproperty = mproperty + self.location = location + mclassdef.mpropdefs.add(self) + mproperty.mpropdefs.add(self) + end + + # Internal name combining the module, the class and the property + # Example: "mymodule#MyClass#mymethod" + redef fun to_s + do + return "{mclassdef}#{mproperty}" + end + + # Is self the definition that introduce the property? + fun is_intro: Bool do return mproperty.intro == self + + # Return the next definition in linearization of `mtype`. + # If there is no next method then null is returned. + # + # This method is used to determine what method is called by a super. + # + # FIXME: NOT YET IMPLEMENTED + # + # REQUIRE: not mtype.need_anchor + fun lookup_next_definition(mmodule: MModule, mtype: MType): nullable MPROPDEF + do + assert not mtype.need_anchor + return null + end +end + +# A local definition of a method +class MMethodDef + super MPropDef + + redef type MPROPERTY: MMethod + redef type MPROPDEF: MMethodDef + + init(mclassdef: MClassDef, mproperty: MPROPERTY, location: Location) + do + super + end + + # The signature attached to the property definition + var msignature: nullable MSignature writable = null +end + +# A local definition of an attribute +class MAttributeDef + super MPropDef + + redef type MPROPERTY: MAttribute + redef type MPROPDEF: MAttributeDef + + init(mclassdef: MClassDef, mproperty: MPROPERTY, location: Location) + do + super + end + + # The static type of the attribute + var static_mtype: nullable MType writable = null +end + +# A local definition of a virtual type +class MVirtualTypeDef + super MPropDef + + redef type MPROPERTY: MVirtualTypeProp + redef type MPROPDEF: MVirtualTypeDef + + init(mclassdef: MClassDef, mproperty: MPROPERTY, location: Location) + do + super + end + + # The bound of the virtual type + var bound: nullable MType writable = null +end + +# A kind of class. +# +# * abstract_kind +# * concrete_kind +# * interface_kind +# * enum_kind +# * extern_kind +# +# Note this class is basically an enum. +# FIXME: use a real enum once user-defined enums are available +class MClassKind + redef var to_s: String + + # Is a constructor required? + var need_init: Bool + private init(s: String, need_init: Bool) + do + self.to_s = s + self.need_init = need_init + end +end + +fun abstract_kind: MClassKind do return once new MClassKind("abstract class", true) +fun concrete_kind: MClassKind do return once new MClassKind("class", true) +fun interface_kind: MClassKind do return once new MClassKind("interface", false) +fun enum_kind: MClassKind do return once new MClassKind("enum", false) +fun extern_kind: MClassKind do return once new MClassKind("extern", false) diff --git a/src/model/model_base.nit b/src/model/model_base.nit new file mode 100644 index 0000000..834a731 --- /dev/null +++ b/src/model/model_base.nit @@ -0,0 +1,291 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +module model_base + +import poset +import location + +# Simple way to store an HashMap[K, Array[V]] +# FIXME: this should move to its own module +class MultiHashMap[K: Object, V] + super HashMap[K, Array[V]] + + # Add `v' to the array associated with `k'. + # If there is no array associated, then create it. + fun add_one(k: K, v: V) + do + if self.has_key(k) then + self[k].add(v) + else + self[k] = [v] + end + end + + init do end +end + +# Simple way to store an HashMap[K1, HashMap[K2, V]] +# FIXME: this should move to its own module +class HashMap2[K1: Object, K2: Object, V] + private var level1: HashMap[K1, HashMap[K2, V]] = new HashMap[K1, HashMap[K2, V]] + fun [](k1: K1, k2: K2): nullable V + do + var level1 = self.level1 + if not level1.has_key(k1) then return null + var level2 = level1[k1] + if not level2.has_key(k2) then return null + return level2[k2] + end + fun []=(k1: K1, k2: K2, v: V) + do + var level1 = self.level1 + var level2: HashMap[K2, V] + if not level1.has_key(k1) then + level2 = new HashMap[K2, V] + level1[k1] = level2 + else + level2 = level1[k1] + end + level2[k2] = v + end +end + +# Simple way to store an HashMap[K1, HashMap[K2, HashMap[K3, V]]] +# FIXME: this should move to its own module +class HashMap3[K1: Object, K2: Object, K3: Object, V] + private var level1: HashMap[K1, HashMap2[K2, K3, V]] = new HashMap[K1, HashMap2[K2, K3, V]] + fun [](k1: K1, k2: K2, k3: K3): nullable V + do + var level1 = self.level1 + if not level1.has_key(k1) then return null + var level2 = level1[k1] + return level2[k2, k3] + end + fun []=(k1: K1, k2: K2, k3: K3, v: V) + do + var level1 = self.level1 + var level2: HashMap2[K2, K3, V] + if not level1.has_key(k1) then + level2 = new HashMap2[K2, K3, V] + level1[k1] = level2 + else + level2 = level1[k1] + end + level2[k2, k3] = v + end +end + +# The container class of a Nit object-oriented model. +# A model knows modules, classes and properties and can retrieve them. +class Model + # All known modules + var mmodules: Array[MModule] = new Array[MModule] + + # Module nesting hierarchy. + # where mainmodule < mainmodule::nestedmodule + var mmodule_nesting_hierarchy: POSet[MModule] = new POSet[MModule] + + # Full module importation hierarchy including private or nested links. + var mmodule_importation_hierarchy: POSet[MModule] = new POSet[MModule] + + # Collections of modules grouped by their short names + private var mmodules_by_name: MultiHashMap[String, MModule] = new MultiHashMap[String, MModule] + + # Return all module named `name' + # If such a module does not exist, null is returned (instead of an empty array) + # + # Visibility or modules are not considered + fun get_mmodules_by_name(name: String): nullable Array[MModule] + do + if mmodules_by_name.has_key(name) then + return mmodules_by_name[name] + else + return null + end + end +end + +# A Nit module is usually associated with a Nit source file. +# Modules can be nested (see `direct_owner', `public_owner', and `in_nesting') +class MModule + # The model considered + var model: Model + + # The direct nesting module, return null if self is not nested (ie. is a top-level module) + var direct_owner: nullable MModule + + # The short name of the module + var name: String + + # The origin of the definition + var location: Location + + # Alias for `name' + redef fun to_s do return self.name + + # The view of the module in the module_nesting_hierarchy + var in_nesting: POSetElement[MModule] + + # The view of the module in the module_importation_hierarchy + var in_importation: POSetElement[MModule] + + # The canonical name of the module + # Example: "owner::name" + fun full_name: String + do + var owner = self.public_owner + if owner == null then + return self.name + else + return "{owner.full_name}::{self.name}" + end + end + + # Create a new empty module and register it to a model + # `direct_owner' is the direct owner (null if top-level module) + init(model: Model, direct_owner: nullable MModule, name: String, location: Location) + do + self.model = model + self.name = name + self.location = location + model.mmodules_by_name.add_one(name, self) + model.mmodules.add(self) + self.in_nesting = model.mmodule_nesting_hierarchy.add_node(self) + self.direct_owner = direct_owner + if direct_owner != null then + model.mmodule_nesting_hierarchy.add_edge(direct_owner, self) + end + self.in_importation = model.mmodule_importation_hierarchy.add_node(self) + end + + # Register the imported modules (ie "import some_module") + # This function can only invoked once by mmodule. + # The visibility must be set with `se_visibility_for'. + fun set_imported_mmodules(imported_mmodules: Array[MModule]) + do + assert unique_invocation: self.in_importation.direct_greaters.is_empty + for m in imported_mmodules do + self.model.mmodule_importation_hierarchy.add_edge(self, m) + end + end + + private var intrude_mmodules: HashSet[MModule] = new HashSet[MModule] + private var public_mmodules: HashSet[MModule] = new HashSet[MModule] + private var private_mmodules: HashSet[MModule] = new HashSet[MModule] + + # Return the visibility level of an imported module `m` + fun visibility_for(m: MModule): MVisibility + do + if m == self then return intrude_visibility + if self.intrude_mmodules.has(m) then return intrude_visibility + if self.public_mmodules.has(m) then return public_visibility + if self.private_mmodules.has(m) then return private_visibility + return none_visibility + end + + # Set the visibility of an imported module + # REQUIRE: the visibility of the modules imported by `m' are already set for `m' + fun set_visibility_for(m: MModule, v: MVisibility) + do + if v == intrude_visibility then + self.intrude_mmodules.add(m) + self.intrude_mmodules.add_all(m.intrude_mmodules) + self.public_mmodules.add_all(m.public_mmodules) + self.private_mmodules.add_all(m.private_mmodules) + else if v == public_visibility then + self.public_mmodules.add(m) + self.public_mmodules.add_all(m.intrude_mmodules) + self.public_mmodules.add_all(m.public_mmodules) + else if v == private_visibility then + self.private_mmodules.add(m) + self.private_mmodules.add_all(m.intrude_mmodules) + self.private_mmodules.add_all(m.public_mmodules) + else + print "{self} visibility for {m} = {v}" + abort # invalid visibility + end + end + + # The first module in the nesting hierarchy to export self as public + # This function is used to determine the canonical name of modules, classes and properties. + # REQUIRE: the visibility of all nesting modules is already set for `m'. + fun public_owner: nullable MModule + do + var res = self.direct_owner + var last = res + while last != null do + if last.visibility_for(self) >= public_visibility then res = last + last = last.direct_owner + end + return res + end + + # Return true if a class or a property introduced in `intro_mmodule' with a visibility of 'visibility' is visible in self. + fun is_visible(intro_mmodule: MModule, visibility: MVisibility): Bool + do + var v = visibility_for(intro_mmodule) + if v == intrude_visibility then + return visibility >= private_visibility + else if v == public_visibility then + return visibility > private_visibility + else if v == private_visibility then + return visibility > private_visibility + else if v == none_visibility then + return false + else + abort + end + end +end + +# A visibility (for modules, class and properties) +# Valid visibility are: +# +# * intrude_visibility +# * public_visibility +# * protected_visibility +# * none_visibility +# +# Note this class is basically an enum. +# FIXME: use a real enum once user-defined enums are available +class MVisibility + super Comparable + redef type OTHER: MVisibility + + redef var to_s: String + + private var level: Int + + private init(s: String, level: Int) + do + self.to_s = s + self.level = level + end + + # Is self give less visibility than other + # none < private < protected < public < intrude + redef fun <(other) + do + return self.level < other.level + end +end + +fun intrude_visibility: MVisibility do return once new MVisibility("intrude", 4) +fun public_visibility: MVisibility do return once new MVisibility("public", 4) +fun protected_visibility: MVisibility do return once new MVisibility("protected", 3) +fun private_visibility: MVisibility do return once new MVisibility("private", 2) +fun none_visibility: MVisibility do return once new MVisibility("none", 2) diff --git a/src/modelbuilder.nit b/src/modelbuilder.nit new file mode 100644 index 0000000..752fa6a --- /dev/null +++ b/src/modelbuilder.nit @@ -0,0 +1,1401 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Load nit source files and build the associated model +# +# FIXME better doc +# +# FIXME split this module into submodules +# FIXME add missing error checks +module modelbuilder + +import parser +import model +import poset +import opts +import toolcontext + +### + +redef class ToolContext + # Option --path + readable var _opt_path: OptionArray = new OptionArray("Set include path for loaders (may be used more than once)", "-I", "--path") + + # Option --only-metamodel + readable var _opt_only_metamodel: OptionBool = new OptionBool("Stop after meta-model processing", "--only-metamodel") + + # Option --only-parse + readable var _opt_only_parse: OptionBool = new OptionBool("Only proceed to parse step of loaders", "--only-parse") + + redef init + do + super + option_context.add_option(opt_path, opt_only_parse, opt_only_metamodel) + end +end + +# A model builder know how to load nit source files and build the associated model +# The important function is `parse_and_build' that does all the job. +# The others function can be used for specific tasks +class ModelBuilder + # The model where new modules, classes and properties are added + var model: Model + + # The toolcontext used to control the interaction with the user (getting options and displaying messages) + var toolcontext: ToolContext + + # Instantiate a modelbuilder for a model and a toolcontext + # Important, the options of the toolcontext must be correctly set (parse_option already called) + init(model: Model, toolcontext: ToolContext) + do + self.model = model + self.toolcontext = toolcontext + + # Setup the paths value + paths.append(toolcontext.opt_path.value) + + var path_env = once ("NIT_PATH".to_symbol).environ + if not path_env.is_empty then + paths.append(path_env.split_with(':')) + end + + path_env = once ("NIT_DIR".to_symbol).environ + if not path_env.is_empty then + var libname = "{path_env}/lib" + if libname.file_exists then paths.add(libname) + end + + var libname = "{sys.program_name.dirname}/../lib" + if libname.file_exists then paths.add(libname.simplify_path) + end + + # Load and analyze a bunch of modules. + # `modules' can contains filenames or module names. + # Imported modules are automatically loaded, builds and analysed. + # The result is the corresponding built modules. + # Errors and warnings are printed with the toolcontext. + # + # FIXME: Maybe just let the client do the loop (instead of playing with Sequences) + fun parse_and_build(modules: Sequence[String]): Array[MModule] + do + var time0 = get_time + # Parse and recursively load + self.toolcontext.info("*** PARSE ***", 1) + var mmodules = new Array[MModule] + for a in modules do + var nmodule = self.load_module(null, a) + if nmodule == null then continue # Skip error + mmodules.add(nmodule.mmodule.as(not null)) + end + var time1 = get_time + self.toolcontext.info("*** END PARSE: {time1-time0} ***", 2) + + self.toolcontext.check_errors + + # Build the model + self.toolcontext.info("*** BUILD MODEL ***", 1) + self.build_all_classes + var time2 = get_time + self.toolcontext.info("*** END BUILD MODEL: {time2-time1} ***", 2) + + self.toolcontext.check_errors + + return mmodules + end + + # Return a class named `name' visible by the module `mmodule'. + # Visibility in modules is correctly handled. + # If no such a class exists, then null is returned. + # If more than one class exists, then an error on `anode' is displayed and null is returned. + # FIXME: add a way to handle class name conflict + fun try_get_mclass_by_name(anode: ANode, mmodule: MModule, name: String): nullable MClass + do + var classes = model.get_mclasses_by_name(name) + if classes == null then + return null + end + + var res: nullable MClass = null + for mclass in classes do + if not mmodule.in_importation <= mclass.intro_mmodule then continue + if not mmodule.is_visible(mclass.intro_mmodule, mclass.visibility) then continue + if res == null then + res = mclass + else + error(anode, "Ambigous class name '{name}'; conflict between {mclass.full_name} and {res.full_name}") + return null + end + end + return res + end + + # Return a property named `name' on the type `mtype' visible in the module `mmodule'. + # Visibility in modules is correctly handled. + # Protected properties are returned (it is up to the caller to check and reject protected properties). + # If no such a property exists, then null is returned. + # If more than one property exists, then an error on `anode' is displayed and null is returned. + # FIXME: add a way to handle property name conflict + fun try_get_mproperty_by_name2(anode: ANode, mmodule: MModule, mtype: MType, name: String): nullable MProperty + do + var props = self.model.get_mproperties_by_name(name) + if props == null then + return null + end + + var cache = self.try_get_mproperty_by_name2_cache[mmodule, mtype, name] + if cache != null then return cache + + var res: nullable MProperty = null + var ress: nullable Array[MProperty] = null + for mprop in props do + if not mtype.has_mproperty(mmodule, mprop) then continue + if not mmodule.is_visible(mprop.intro_mclassdef.mmodule, mprop.visibility) then continue + if res == null then + res = mprop + else + var restype = res.intro_mclassdef.bound_mtype + var mproptype = mprop.intro_mclassdef.bound_mtype + if restype.is_subtype(mmodule, null, mproptype) then + # we keep res + else if mproptype.is_subtype(mmodule, null, restype) then + res = mprop + else + if ress == null then ress = new Array[MProperty] + ress.add(mprop) + end + end + end + if ress != null then + var restype = res.intro_mclassdef.bound_mtype + for mprop in ress do + var mproptype = mprop.intro_mclassdef.bound_mtype + if not restype.is_subtype(mmodule, null, mproptype) then + self.error(anode, "Ambigous property name '{name}' for {mtype}; conflict between {mprop.full_name} and {res.full_name}") + return null + end + end + end + + self.try_get_mproperty_by_name2_cache[mmodule, mtype, name] = res + return res + end + + private var try_get_mproperty_by_name2_cache: HashMap3[MModule, MType, String, nullable MProperty] = new HashMap3[MModule, MType, String, nullable MProperty] + + + # Alias for try_get_mproperty_by_name2(anode, mclassdef.mmodule, mclassdef.mtype, name) + fun try_get_mproperty_by_name(anode: ANode, mclassdef: MClassDef, name: String): nullable MProperty + do + return try_get_mproperty_by_name2(anode, mclassdef.mmodule, mclassdef.bound_mtype, name) + end + + # The list of directories to search for top level modules + # The list is initially set with : + # * the toolcontext --path option + # * the NIT_PATH environment variable + # * some heuristics including the NIT_DIR environment variable and the progname of the process + # Path can be added (or removed) by the client + var paths: Array[String] = new Array[String] + + # Get a module by its short name; if required, the module is loaded, parsed and its hierarchies computed. + # If `mmodule' is set, then the module search starts from it up to the top level (see `paths'); + # if `mmodule' is null then the module is searched in the top level only. + # If no module exists or there is a name conflict, then an error on `anode' is displayed and null is returned. + # FIXME: add a way to handle module name conflict + fun get_mmodule_by_name(anode: ANode, mmodule: nullable MModule, name: String): nullable MModule + do + var origmmodule = mmodule + var modules = model.get_mmodules_by_name(name) + + var lastmodule = mmodule + while mmodule != null do + var dirname = mmodule.location.file.filename.dirname + + # Determine the owner + var owner: nullable MModule + if dirname.basename("") != mmodule.name then + owner = mmodule.direct_owner + else + owner = mmodule + end + + # First, try the already known nested modules + if modules != null then + for candidate in modules do + if candidate.direct_owner == owner then + return candidate + end + end + end + + # Second, try the directory to find a file + var try_file = dirname + "/" + name + ".nit" + if try_file.file_exists then + var res = self.load_module(owner, try_file.simplify_path) + if res == null then return null # Forward error + return res.mmodule.as(not null) + end + + # Third, try if the requested module is itself an owner + try_file = dirname + "/" + name + "/" + name + ".nit" + if try_file.file_exists then + var res = self.load_module(owner, try_file.simplify_path) + if res == null then return null # Forward error + return res.mmodule.as(not null) + end + + lastmodule = mmodule + mmodule = mmodule.direct_owner + end + + if modules != null then + for candidate in modules do + if candidate.direct_owner == null then + return candidate + end + end + end + + # Look at some known directories + var lookpaths = self.paths + + # Look in the directory of the last module also (event if not in the path) + if lastmodule != null then + var dirname = lastmodule.location.file.filename.dirname + if dirname.basename("") == lastmodule.name then + dirname = dirname.dirname + end + if not lookpaths.has(dirname) then + lookpaths = lookpaths.to_a + lookpaths.add(dirname) + end + end + + var candidate: nullable String = null + for dirname in lookpaths do + var try_file = (dirname + "/" + name + ".nit").simplify_path + if try_file.file_exists then + if candidate == null then + candidate = try_file + else if candidate != try_file then + error(anode, "Error: conflicting module file for {name}: {candidate} {try_file}") + end + end + try_file = (dirname + "/" + name + "/" + name + ".nit").simplify_path + if try_file.file_exists then + if candidate == null then + candidate = try_file + else if candidate != try_file then + error(anode, "Error: conflicting module file for {name}: {candidate} {try_file}") + end + end + end + if candidate == null then + if origmmodule != null then + error(anode, "Error: cannot find module {name} from {origmmodule}") + else + error(anode, "Error: cannot find module {name}") + end + return null + end + var res = self.load_module(mmodule, candidate) + if res == null then return null # Forward error + return res.mmodule.as(not null) + end + + # Try to load a module using a path. + # Display an error if there is a problem (IO / lexer / parser) and return null + # Note: usually, you do not need this method, use `get_mmodule_by_name` instead. + fun load_module(owner: nullable MModule, filename: String): nullable AModule + do + if not filename.file_exists then + self.toolcontext.error(null, "Error: file {filename} not found.") + return null + end + + var x = if owner != null then owner.to_s else "." + self.toolcontext.info("load module {filename} in {x}", 2) + + # Load the file + var file = new IFStream.open(filename) + var lexer = new Lexer(new SourceFile(filename, file)) + var parser = new Parser(lexer) + var tree = parser.parse + file.close + + # Handle lexer and parser error + var nmodule = tree.n_base + if nmodule == null then + var neof = tree.n_eof + assert neof isa AError + error(neof, neof.message) + return null + end + + # Check the module name + var mod_name = filename.basename(".nit") + var decl = nmodule.n_moduledecl + if decl == null then + #warning(nmodule, "Warning: Missing 'module' keyword") #FIXME: NOT YET FOR COMPATIBILITY + else + var decl_name = decl.n_name.n_id.text + if decl_name != mod_name then + error(decl.n_name, "Error: module name missmatch; declared {decl_name} file named {mod_name}") + end + end + + # Create the module + var mmodule = new MModule(model, owner, mod_name, nmodule.location) + nmodule.mmodule = mmodule + nmodules.add(nmodule) + self.mmodule2nmodule[mmodule] = nmodule + + build_module_importation(nmodule) + + return nmodule + end + + # Analysis the module importation and fill the module_importation_hierarchy + private fun build_module_importation(nmodule: AModule) + do + if nmodule.is_importation_done then return + var mmodule = nmodule.mmodule.as(not null) + var stdimport = true + var imported_modules = new Array[MModule] + for aimport in nmodule.n_imports do + stdimport = false + if not aimport isa AStdImport then + continue + end + var mod_name = aimport.n_name.n_id.text + var sup = self.get_mmodule_by_name(aimport.n_name, mmodule, mod_name) + if sup == null then continue # Skip error + imported_modules.add(sup) + var mvisibility = aimport.n_visibility.mvisibility + mmodule.set_visibility_for(sup, mvisibility) + end + if stdimport then + var mod_name = "standard" + var sup = self.get_mmodule_by_name(nmodule, null, mod_name) + if sup != null then # Skip error + imported_modules.add(sup) + mmodule.set_visibility_for(sup, public_visibility) + end + end + self.toolcontext.info("{mmodule} imports {imported_modules.join(", ")}", 3) + mmodule.set_imported_mmodules(imported_modules) + nmodule.is_importation_done = true + end + + # All the loaded modules + var nmodules: Array[AModule] = new Array[AModule] + + # Build the classes of all modules `nmodules'. + private fun build_all_classes + do + for nmodule in self.nmodules do + build_classes(nmodule) + end + end + + # Visit the AST and create the MClass objects + private fun build_a_mclass(nmodule: AModule, nclassdef: AClassdef) + do + var mmodule = nmodule.mmodule.as(not null) + + var name: String + var nkind: nullable AClasskind + var mkind: MClassKind + var nvisibility: nullable AVisibility + var mvisibility: nullable MVisibility + var arity = 0 + if nclassdef isa AStdClassdef then + name = nclassdef.n_id.text + nkind = nclassdef.n_classkind + mkind = nkind.mkind + nvisibility = nclassdef.n_visibility + mvisibility = nvisibility.mvisibility + arity = nclassdef.n_formaldefs.length + else if nclassdef isa ATopClassdef then + name = "Object" + nkind = null + mkind = interface_kind + nvisibility = null + mvisibility = public_visibility + else if nclassdef isa AMainClassdef then + name = "Sys" + nkind = null + mkind = concrete_kind + nvisibility = null + mvisibility = public_visibility + else + abort + end + + var mclass = try_get_mclass_by_name(nclassdef, mmodule, name) + if mclass == null then + mclass = new MClass(mmodule, name, arity, mkind, mvisibility) + #print "new class {mclass}" + else if nclassdef isa AStdClassdef and nclassdef.n_kwredef == null then + error(nclassdef, "Redef error: {name} is an imported class. Add the redef keyword to refine it.") + return + else if mclass.arity != arity then + error(nclassdef, "Redef error: Formal parameter arity missmatch; got {arity}, expected {mclass.arity}.") + return + else if nkind != null and mkind != concrete_kind and mclass.kind != mkind then + error(nkind, "Error: refinement changed the kind from a {mclass.kind} to a {mkind}") + else if nvisibility != null and mvisibility != public_visibility and mclass.visibility != mvisibility then + error(nvisibility, "Error: refinement changed the visibility from a {mclass.visibility} to a {mvisibility}") + end + nclassdef.mclass = mclass + end + + # Visit the AST and create the MClassDef objects + private fun build_a_mclassdef(nmodule: AModule, nclassdef: AClassdef) + do + var mmodule = nmodule.mmodule.as(not null) + var objectclass = try_get_mclass_by_name(nmodule, mmodule, "Object") + var mclass = nclassdef.mclass.as(not null) + #var mclassdef = nclassdef.mclassdef.as(not null) + + var names = new Array[String] + var bounds = new Array[MType] + if nclassdef isa AStdClassdef and mclass.arity > 0 then + # Collect formal parameter names + for i in [0..mclass.arity[ do + var nfd = nclassdef.n_formaldefs[i] + var ptname = nfd.n_id.text + if names.has(ptname) then + error(nfd, "Error: A formal parameter type `{ptname}' already exists") + return + end + names.add(ptname) + end + + # Revolve bound for formal parameter names + for i in [0..mclass.arity[ do + var nfd = nclassdef.n_formaldefs[i] + var nfdt = nfd.n_type + if nfdt != null then + var bound = resolve_mtype(nclassdef, nfdt) + if bound == null then return # Forward error + if bound.need_anchor then + # No F-bounds! + error(nfd, "Error: Formal parameter type `{names[i]}' bounded with a formal parameter type") + else + bounds.add(bound) + end + else if mclass.mclassdefs.is_empty then + # No bound, then implicitely bound by nullable Object + bounds.add(objectclass.mclass_type.as_nullable) + else + # Inherit the bound + bounds.add(mclass.mclassdefs.first.bound_mtype.as(MGenericType).arguments[i]) + end + end + end + + var bound_mtype = mclass.get_mtype(bounds) + var mclassdef = new MClassDef(mmodule, bound_mtype, nclassdef.location, names) + nclassdef.mclassdef = mclassdef + self.mclassdef2nclassdef[mclassdef] = nclassdef + + if mclassdef.is_intro then + self.toolcontext.info("{mclassdef} introduces new {mclass.kind} {mclass.full_name}", 3) + else + self.toolcontext.info("{mclassdef} refine {mclass.kind} {mclass.full_name}", 3) + end + end + + # Visit the AST and set the super-types of the MClass objects (ie compute the inheritance) + private fun build_a_mclassdef_inheritance(nmodule: AModule, nclassdef: AClassdef) + do + var mmodule = nmodule.mmodule.as(not null) + var objectclass = try_get_mclass_by_name(nmodule, mmodule, "Object") + var mclass = nclassdef.mclass.as(not null) + var mclassdef = nclassdef.mclassdef.as(not null) + + var specobject = true + var supertypes = new Array[MClassType] + if nclassdef isa AStdClassdef then + for nsc in nclassdef.n_superclasses do + specobject = false + var ntype = nsc.n_type + var mtype = resolve_mtype(nclassdef, ntype) + if mtype == null then continue # Skip because of error + if not mtype isa MClassType then + error(ntype, "Error: supertypes cannot be a formal type") + return + end + supertypes.add mtype + #print "new super : {mclass} < {mtype}" + end + end + if specobject and mclass.name != "Object" and objectclass != null and mclassdef.is_intro then + supertypes.add objectclass.mclass_type + end + + mclassdef.set_supertypes(supertypes) + if not supertypes.is_empty then self.toolcontext.info("{mclassdef} new super-types: {supertypes.join(", ")}", 3) + end + + # Check the validity of the specialization heirarchy + # FIXME Stub implementation + private fun check_supertypes(nmodule: AModule, nclassdef: AClassdef) + do + var mmodule = nmodule.mmodule.as(not null) + var objectclass = try_get_mclass_by_name(nmodule, mmodule, "Object") + var mclass = nclassdef.mclass.as(not null) + var mclassdef = nclassdef.mclassdef.as(not null) + end + + # Build the classes of the module `nmodule'. + # REQUIRE: classes of imported modules are already build. (let `build_all_classes' do the job) + private fun build_classes(nmodule: AModule) + do + # Force building recursively + if nmodule.build_classes_is_done then return + var mmodule = nmodule.mmodule.as(not null) + for imp in mmodule.in_importation.direct_greaters do + build_classes(mmodule2nmodule[imp]) + end + + # Create all classes + for nclassdef in nmodule.n_classdefs do + self.build_a_mclass(nmodule, nclassdef) + end + + # Create all classdefs + for nclassdef in nmodule.n_classdefs do + self.build_a_mclassdef(nmodule, nclassdef) + end + + # Create inheritance on all classdefs + for nclassdef in nmodule.n_classdefs do + self.build_a_mclassdef_inheritance(nmodule, nclassdef) + end + + # TODO: Check that the super-class is not intrusive + + # TODO: Check that the super-class is not already known (by transitivity) + + for nclassdef in nmodule.n_classdefs do + self.build_properties(nclassdef) + end + + nmodule.build_classes_is_done = true + end + + # Register the nmodule associated to each mmodule + # FIXME: why not refine the MModule class with a nullable attribute? + var mmodule2nmodule: HashMap[MModule, AModule] = new HashMap[MModule, AModule] + # Register the nclassdef associated to each mclassdef + # FIXME: why not refine the MClassDef class with a nullable attribute? + var mclassdef2nclassdef: HashMap[MClassDef, AClassdef] = new HashMap[MClassDef, AClassdef] + # Register the npropdef associated to each mpropdef + # FIXME: why not refine the MPropDef class with a nullable attribute? + var mpropdef2npropdef: HashMap[MPropDef, APropdef] = new HashMap[MPropDef, APropdef] + + # Build the properties of `nclassdef'. + # REQUIRE: all superclasses are built. + private fun build_properties(nclassdef: AClassdef) + do + # Force building recursively + if nclassdef.build_properties_is_done then return + var mclassdef = nclassdef.mclassdef.as(not null) + if mclassdef.in_hierarchy == null then return # Skip error + for superclassdef in mclassdef.in_hierarchy.direct_greaters do + build_properties(mclassdef2nclassdef[superclassdef]) + end + + for npropdef in nclassdef.n_propdefs do + npropdef.build_property(self, nclassdef) + end + for npropdef in nclassdef.n_propdefs do + npropdef.build_signature(self, nclassdef) + end + for npropdef in nclassdef.n_propdefs do + npropdef.check_signature(self, nclassdef) + end + process_default_constructors(nclassdef) + nclassdef.build_properties_is_done = true + end + + # Introduce or inherit default constructor + # This is the last part of `build_properties'. + private fun process_default_constructors(nclassdef: AClassdef) + do + var mclassdef = nclassdef.mclassdef.as(not null) + + # Are we a refinement + if not mclassdef.is_intro then return + + # Is the class forbid constructors? + if not mclassdef.mclass.kind.need_init then return + + # Is there already a constructor defined? + for mpropdef in mclassdef.mpropdefs do + if not mpropdef isa MMethodDef then continue + if mpropdef.mproperty.is_init then return + end + + if not nclassdef isa AStdClassdef then return + + var mmodule = nclassdef.mclassdef.mmodule + # Do we inherit for a constructor? + var combine = new Array[MMethod] + var inhc: nullable MClass = null + for st in mclassdef.supertypes do + var c = st.mclass + if not c.kind.need_init then continue + st = st.anchor_to(mmodule, nclassdef.mclassdef.bound_mtype) + var candidate = self.try_get_mproperty_by_name2(nclassdef, mmodule, st, "init").as(nullable MMethod) + if candidate != null and candidate.intro.msignature.arity == 0 then + combine.add(candidate) + continue + end + var inhc2 = c.inherit_init_from + if inhc2 == null then inhc2 = c + if inhc2 == inhc then continue + if inhc != null then + self.error(nclassdef, "Cannot provide a defaut constructor: conflict for {inhc} and {c}") + else + inhc = inhc2 + end + end + if combine.is_empty and inhc != null then + # TODO: actively inherit the consturctor + self.toolcontext.info("{mclassdef} inherits all constructors from {inhc}", 3) + mclassdef.mclass.inherit_init_from = inhc + return + end + if not combine.is_empty and inhc != null then + self.error(nclassdef, "Cannot provide a defaut constructor: conflict for {combine.join(", ")} and {inhc}") + return + end + + if not combine.is_empty then + nclassdef.super_inits = combine + var mprop = new MMethod(mclassdef, "init", mclassdef.mclass.visibility) + var mpropdef = new MMethodDef(mclassdef, mprop, nclassdef.location) + var param_names = new Array[String] + var param_types = new Array[MType] + var msignature = new MSignature(param_names, param_types, null, -1) + mpropdef.msignature = msignature + mprop.is_init = true + nclassdef.mfree_init = mpropdef + self.toolcontext.info("{mclassdef} gets a free empty constructor {mpropdef}{msignature}", 3) + return + end + + # Collect undefined attributes + var param_names = new Array[String] + var param_types = new Array[MType] + for npropdef in nclassdef.n_propdefs do + if npropdef isa AAttrPropdef and npropdef.n_expr == null then + param_names.add(npropdef.mpropdef.mproperty.name.substring_from(1)) + var ret_type = npropdef.mpropdef.static_mtype + if ret_type == null then return + param_types.add(ret_type) + end + end + + var mprop = new MMethod(mclassdef, "init", mclassdef.mclass.visibility) + var mpropdef = new MMethodDef(mclassdef, mprop, nclassdef.location) + var msignature = new MSignature(param_names, param_types, null, -1) + mpropdef.msignature = msignature + mprop.is_init = true + nclassdef.mfree_init = mpropdef + self.toolcontext.info("{mclassdef} gets a free constructor for attributes {mpropdef}{msignature}", 3) + end + + # Return the static type associated to the node `ntype'. + # `classdef' is the context where the call is made (used to understand formal types) + # The mmodule used as context is `nclassdef.mmodule' + # In case of problem, an error is displayed on `ntype' and null is returned. + # FIXME: the name "resolve_mtype" is awful + fun resolve_mtype(nclassdef: AClassdef, ntype: AType): nullable MType + do + var name = ntype.n_id.text + var mclassdef = nclassdef.mclassdef + var mmodule = nclassdef.parent.as(AModule).mmodule.as(not null) + var res: MType + + # Check virtual type + if mclassdef != null then + var prop = try_get_mproperty_by_name(ntype, mclassdef, name).as(nullable MVirtualTypeProp) + if prop != null then + if not ntype.n_types.is_empty then + error(ntype, "Type error: formal type {name} cannot have formal parameters.") + end + res = prop.mvirtualtype + if ntype.n_kwnullable != null then res = res.as_nullable + return res + end + end + + # Check parameter type + if mclassdef != null and mclassdef.parameter_names.has(name) then + if not ntype.n_types.is_empty then + error(ntype, "Type error: formal type {name} cannot have formal parameters.") + end + for i in [0..mclassdef.parameter_names.length[ do + if mclassdef.parameter_names[i] == name then + res = mclassdef.mclass.mclass_type.as(MGenericType).arguments[i] + if ntype.n_kwnullable != null then res = res.as_nullable + return res + end + end + abort + end + + # Check class + var mclass = try_get_mclass_by_name(ntype, mmodule, name) + if mclass != null then + var arity = ntype.n_types.length + if arity != mclass.arity then + if arity == 0 then + error(ntype, "Type error: '{name}' is a generic class.") + else if mclass.arity == 0 then + error(ntype, "Type error: '{name}' is not a generic class.") + else + error(ntype, "Type error: '{name}' has {mclass.arity} parameters ({arity} are provided).") + end + return null + end + if arity == 0 then + res = mclass.mclass_type + if ntype.n_kwnullable != null then res = res.as_nullable + return res + else + var mtypes = new Array[MType] + for nt in ntype.n_types do + var mt = resolve_mtype(nclassdef, nt) + if mt == null then return null # Forward error + mtypes.add(mt) + end + res = mclass.get_mtype(mtypes) + if ntype.n_kwnullable != null then res = res.as_nullable + return res + end + end + + # If everything fail, then give up :( + error(ntype, "Type error: class {name} not found in module {mmodule}.") + return null + end + + # Helper function to display an error on a node. + # Alias for `self.toolcontext.error(n.hot_location, text)' + fun error(n: ANode, text: String) + do + self.toolcontext.error(n.hot_location, text) + end + + # Helper function to display a warning on a node. + # Alias for: `self.toolcontext.warning(n.hot_location, text)' + fun warning(n: ANode, text: String) + do + self.toolcontext.warning(n.hot_location, text) + end +end + +redef class AModule + # The associated MModule once build by a `ModelBuilder' + var mmodule: nullable MModule + # Flag that indicate if the importation is already completed + var is_importation_done: Bool = false + # Flag that indicate if the class and prop building is already completed + var build_classes_is_done: Bool = false +end + +redef class MClass + # The class whose self inherit all the constructors. + # FIXME: this is needed to implement the crazy constructor mixin thing of the of old compiler. We need to think what to do with since this cannot stay in the modelbuilder + var inherit_init_from: nullable MClass = null +end + +redef class AClassdef + # The associated MClass once build by a `ModelBuilder' + var mclass: nullable MClass + # The associated MClassDef once build by a `ModelBuilder' + var mclassdef: nullable MClassDef + var build_properties_is_done: Bool = false + # The list of super-constructor to call at the start of the free constructor + # FIXME: this is needed to implement the crazy constructor thing of the of old compiler. We need to think what to do with since this cannot stay in the modelbuilder + var super_inits: nullable Collection[MMethod] = null + + # The free init (implicitely constructed by the class if required) + var mfree_init: nullable MMethodDef = null +end + +redef class AClasskind + # The class kind associated with the AST node class + private fun mkind: MClassKind is abstract +end +redef class AConcreteClasskind + redef fun mkind do return concrete_kind +end +redef class AAbstractClasskind + redef fun mkind do return abstract_kind +end +redef class AInterfaceClasskind + redef fun mkind do return interface_kind +end +redef class AEnumClasskind + redef fun mkind do return enum_kind +end +redef class AExternClasskind + redef fun mkind do return extern_kind +end + +redef class AVisibility + # The visibility level associated with the AST node class + private fun mvisibility: MVisibility is abstract +end +redef class AIntrudeVisibility + redef fun mvisibility do return intrude_visibility +end +redef class APublicVisibility + redef fun mvisibility do return public_visibility +end +redef class AProtectedVisibility + redef fun mvisibility do return protected_visibility +end +redef class APrivateVisibility + redef fun mvisibility do return private_visibility +end + + +# + +redef class Prod + # Join the text of all tokens + # Used to get the 'real name' of method definitions. + fun collect_text: String + do + var v = new TextCollectorVisitor + v.enter_visit(self) + assert v.text != "" + return v.text + end +end + +private class TextCollectorVisitor + super Visitor + var text: String = "" + redef fun visit(n) + do + if n isa Token then text += n.text + n.visit_all(self) + end +end + +redef class APropdef + private fun build_property(modelbuilder: ModelBuilder, nclassdef: AClassdef) + do + end + private fun build_signature(modelbuilder: ModelBuilder, nclassdef: AClassdef) + do + end + private fun check_signature(modelbuilder: ModelBuilder, nclassdef: AClassdef) + do + end + private fun new_property_visibility(modelbuilder: ModelBuilder, nclassdef: AClassdef, nvisibility: nullable AVisibility): MVisibility + do + var mvisibility = public_visibility + if nvisibility != null then mvisibility = nvisibility.mvisibility + if nclassdef.mclassdef.mclass.visibility == private_visibility then + if mvisibility == protected_visibility then + assert nvisibility != null + modelbuilder.error(nvisibility, "Error: The only legal visibility for properties in a private class is private.") + else if mvisibility == private_visibility then + assert nvisibility != null + # Not yet + # modelbuilder.warning(nvisibility, "Warning: private is unrequired since the only legal visibility for properties in a private class is private.") + end + mvisibility = private_visibility + end + return mvisibility + end + + private fun check_redef_property_visibility(modelbuilder: ModelBuilder, nclassdef: AClassdef, nvisibility: nullable AVisibility, mprop: MProperty) + do + if nvisibility == null then return + var mvisibility = nvisibility.mvisibility + if mvisibility != mprop.visibility and mvisibility != public_visibility then + modelbuilder.error(nvisibility, "Error: redefinition changed the visibility from a {mprop.visibility} to a {mvisibility}") + end + end + + private fun check_redef_keyword(modelbuilder: ModelBuilder, nclassdef: AClassdef, kwredef: nullable Token, need_redef: Bool, mprop: MProperty) + do + if kwredef == null then + if need_redef then + modelbuilder.error(self, "Redef error: {nclassdef.mclassdef.mclass}::{mprop.name} is an inherited property. To redefine it, add the redef keyword.") + end + else + if not need_redef then + modelbuilder.error(self, "Error: No property {nclassdef.mclassdef.mclass}::{mprop.name} is inherited. Remove the redef keyword to define a new property.") + end + end + end +end + +redef class AMethPropdef + # The associated MMethodDef once build by a `ModelBuilder' + var mpropdef: nullable MMethodDef + + # The associated super init if any + var super_init: nullable MMethod + redef fun build_property(modelbuilder, nclassdef) + do + var is_init = self isa AInitPropdef + var mclassdef = nclassdef.mclassdef.as(not null) + var name: String + var amethodid = self.n_methid + var name_node: ANode + if amethodid == null then + if self isa AMainMethPropdef then + name = "main" + name_node = self + else if self isa AConcreteInitPropdef then + name = "init" + name_node = self.n_kwinit + else if self isa AExternInitPropdef then + name = "new" + name_node = self.n_kwnew + else + abort + end + else if amethodid isa AIdMethid then + name = amethodid.n_id.text + name_node = amethodid + else + # operator, bracket or assign + name = amethodid.collect_text + name_node = amethodid + + if name == "-" and self.n_signature.n_params.length == 0 then + name = "unary -" + end + end + + var mprop: nullable MMethod = null + if not is_init or n_kwredef != null then mprop = modelbuilder.try_get_mproperty_by_name(name_node, mclassdef, name).as(nullable MMethod) + if mprop == null then + var mvisibility = new_property_visibility(modelbuilder, nclassdef, self.n_visibility) + mprop = new MMethod(mclassdef, name, mvisibility) + mprop.is_init = is_init + self.check_redef_keyword(modelbuilder, nclassdef, n_kwredef, false, mprop) + else + if n_kwredef == null then + if self isa AMainMethPropdef then + # no warning + else + self.check_redef_keyword(modelbuilder, nclassdef, n_kwredef, true, mprop) + end + end + check_redef_property_visibility(modelbuilder, nclassdef, self.n_visibility, mprop) + end + + var mpropdef = new MMethodDef(mclassdef, mprop, self.location) + + self.mpropdef = mpropdef + modelbuilder.mpropdef2npropdef[mpropdef] = self + if mpropdef.is_intro then + modelbuilder.toolcontext.info("{mpropdef} introduces new method {mprop.full_name}", 3) + else + modelbuilder.toolcontext.info("{mpropdef} redefines method {mprop.full_name}", 3) + end + end + + redef fun build_signature(modelbuilder, nclassdef) + do + var mpropdef = self.mpropdef + if mpropdef == null then return # Error thus skiped + var mmodule = mpropdef.mclassdef.mmodule + var nsig = self.n_signature + + # Retrieve info from the signature AST + var param_names = new Array[String] # Names of parameters from the AST + var param_types = new Array[MType] # Types of parameters from the AST + var vararg_rank = -1 + var ret_type: nullable MType = null # Return type from the AST + if nsig != null then + for np in nsig.n_params do + param_names.add(np.n_id.text) + var ntype = np.n_type + if ntype != null then + var mtype = modelbuilder.resolve_mtype(nclassdef, ntype) + if mtype == null then return # Skip error + for i in [0..param_names.length-param_types.length[ do + param_types.add(mtype) + end + if np.n_dotdotdot != null then + if vararg_rank != -1 then + modelbuilder.error(np, "Error: {param_names[vararg_rank]} is already a vararg") + else + vararg_rank = param_names.length - 1 + end + end + end + end + var ntype = nsig.n_type + if ntype != null then + ret_type = modelbuilder.resolve_mtype(nclassdef, ntype) + if ret_type == null then return # Skip errir + end + end + + # Look for some signature to inherit + # FIXME: do not inherit from the intro, but from the most specific + var msignature: nullable MSignature = null + if not mpropdef.is_intro then + msignature = mpropdef.mproperty.intro.msignature + if msignature == null then return # Skip error + else if mpropdef.mproperty.is_init then + # FIXME UGLY: inherit signature from a super-constructor + for msupertype in nclassdef.mclassdef.supertypes do + msupertype = msupertype.anchor_to(mmodule, nclassdef.mclassdef.bound_mtype) + var candidate = modelbuilder.try_get_mproperty_by_name2(self, mmodule, msupertype, mpropdef.mproperty.name) + if candidate != null then + if msignature == null then + msignature = candidate.intro.as(MMethodDef).msignature + end + end + end + end + + # Inherit the signature + if msignature != null and param_names.length != param_types.length and param_names.length == msignature.arity and param_types.length == 0 then + # Parameters are untyped, thus inherit them + param_types = msignature.parameter_mtypes + vararg_rank = msignature.vararg_rank + end + if msignature != null and ret_type == null then + ret_type = msignature.return_mtype + end + + if param_names.length != param_types.length then + # Some parameters are typed, other parameters are not typed. + modelbuilder.warning(nsig.n_params[param_types.length], "Error: Untyped parameter `{param_names[param_types.length]}'.") + return + end + + msignature = new MSignature(param_names, param_types, ret_type, vararg_rank) + mpropdef.msignature = msignature + end + + redef fun check_signature(modelbuilder, nclassdef) + do + var mpropdef = self.mpropdef + if mpropdef == null then return # Error thus skiped + var mmodule = mpropdef.mclassdef.mmodule + var nsig = self.n_signature + var mysignature = self.mpropdef.msignature + if mysignature == null then return # Error thus skiped + + # Lookup for signature in the precursor + # FIXME all precursors should be considered + if not mpropdef.is_intro then + var msignature = mpropdef.mproperty.intro.msignature + if msignature == null then return + + if mysignature.arity != msignature.arity then + var node: ANode + if nsig != null then node = nsig else node = self + modelbuilder.error(node, "Redef Error: {mysignature.arity} parameters found, {msignature.arity} expected. Signature is {mpropdef}{msignature}") + return + end + var precursor_ret_type = msignature.return_mtype + var ret_type = mysignature.return_mtype + if ret_type != null and precursor_ret_type == null then + modelbuilder.error(nsig.n_type.as(not null), "Redef Error: {mpropdef.mproperty} is a procedure, not a function.") + return + end + + if mysignature.arity > 0 then + # Check parameters types + for i in [0..mysignature.arity[ do + var myt = mysignature.parameter_mtypes[i] + var prt = msignature.parameter_mtypes[i] + if not myt.is_subtype(mmodule, nclassdef.mclassdef.bound_mtype, prt) and + not prt.is_subtype(mmodule, nclassdef.mclassdef.bound_mtype, myt) then + modelbuilder.error(nsig.n_params[i], "Redef Error: Wrong type for parameter `{mysignature.parameter_names[i]}'. found {myt}, expected {prt}.") + end + end + end + if precursor_ret_type != null then + if ret_type == null then + # Inherit the return type + ret_type = precursor_ret_type + else if not ret_type.is_subtype(mmodule, nclassdef.mclassdef.bound_mtype, precursor_ret_type) then + modelbuilder.error(nsig.n_type.as(not null), "Redef Error: Wrong return type. found {ret_type}, expected {precursor_ret_type}.") + end + end + end + end +end + +redef class AAttrPropdef + # The associated MAttributeDef once build by a `ModelBuilder' + var mpropdef: nullable MAttributeDef + # The associated getter (read accessor) if any + var mreadpropdef: nullable MMethodDef + # The associated setter (write accessor) if any + var mwritepropdef: nullable MMethodDef + redef fun build_property(modelbuilder, nclassdef) + do + var mclassdef = nclassdef.mclassdef.as(not null) + var mclass = mclassdef.mclass + + var name: String + if self.n_id != null then + name = self.n_id.text + else + name = self.n_id2.text + end + + if mclass.kind == interface_kind or mclassdef.mclass.kind == enum_kind then + modelbuilder.error(self, "Error: Attempt to define attribute {name} in the interface {mclass}.") + else if mclass.kind == enum_kind then + modelbuilder.error(self, "Error: Attempt to define attribute {name} in the enum class {mclass}.") + end + + var nid = self.n_id + if nid != null then + # Old attribute style + var mprop = modelbuilder.try_get_mproperty_by_name(nid, mclassdef, name) + if mprop == null then + var mvisibility = new_property_visibility(modelbuilder, nclassdef, self.n_visibility) + mprop = new MAttribute(mclassdef, name, mvisibility) + self.check_redef_keyword(modelbuilder, nclassdef, self.n_kwredef, false, mprop) + else + assert mprop isa MAttribute + check_redef_property_visibility(modelbuilder, nclassdef, self.n_visibility, mprop) + self.check_redef_keyword(modelbuilder, nclassdef, self.n_kwredef, true, mprop) + end + var mpropdef = new MAttributeDef(mclassdef, mprop, self.location) + self.mpropdef = mpropdef + modelbuilder.mpropdef2npropdef[mpropdef] = self + + var nreadable = self.n_readable + if nreadable != null then + var readname = name.substring_from(1) + var mreadprop = modelbuilder.try_get_mproperty_by_name(nid, mclassdef, readname).as(nullable MMethod) + if mreadprop == null then + var mvisibility = new_property_visibility(modelbuilder, nclassdef, nreadable.n_visibility) + mreadprop = new MMethod(mclassdef, readname, mvisibility) + self.check_redef_keyword(modelbuilder, nclassdef, nreadable.n_kwredef, false, mreadprop) + else + self.check_redef_keyword(modelbuilder, nclassdef, nreadable.n_kwredef, true, mreadprop) + check_redef_property_visibility(modelbuilder, nclassdef, nreadable.n_visibility, mreadprop) + end + var mreadpropdef = new MMethodDef(mclassdef, mreadprop, self.location) + self.mreadpropdef = mreadpropdef + modelbuilder.mpropdef2npropdef[mreadpropdef] = self + end + + var nwritable = self.n_writable + if nwritable != null then + var writename = name.substring_from(1) + "=" + var mwriteprop = modelbuilder.try_get_mproperty_by_name(nid, mclassdef, writename).as(nullable MMethod) + if mwriteprop == null then + var mvisibility = new_property_visibility(modelbuilder, nclassdef, nwritable.n_visibility) + mwriteprop = new MMethod(mclassdef, writename, mvisibility) + self.check_redef_keyword(modelbuilder, nclassdef, nwritable.n_kwredef, false, mwriteprop) + else + self.check_redef_keyword(modelbuilder, nclassdef, nwritable.n_kwredef, true, mwriteprop) + check_redef_property_visibility(modelbuilder, nclassdef, nwritable.n_visibility, mwriteprop) + end + var mwritepropdef = new MMethodDef(mclassdef, mwriteprop, self.location) + self.mwritepropdef = mwritepropdef + modelbuilder.mpropdef2npropdef[mwritepropdef] = self + end + else + # New attribute style + var nid2 = self.n_id2.as(not null) + var mprop = new MAttribute(mclassdef, "@" + name, none_visibility) + var mpropdef = new MAttributeDef(mclassdef, mprop, self.location) + self.mpropdef = mpropdef + modelbuilder.mpropdef2npropdef[mpropdef] = self + + var readname = name + var mreadprop = modelbuilder.try_get_mproperty_by_name(nid2, mclassdef, readname).as(nullable MMethod) + if mreadprop == null then + var mvisibility = new_property_visibility(modelbuilder, nclassdef, self.n_visibility) + mreadprop = new MMethod(mclassdef, readname, mvisibility) + self.check_redef_keyword(modelbuilder, nclassdef, n_kwredef, false, mreadprop) + else + self.check_redef_keyword(modelbuilder, nclassdef, n_kwredef, true, mreadprop) + check_redef_property_visibility(modelbuilder, nclassdef, self.n_visibility, mreadprop) + end + var mreadpropdef = new MMethodDef(mclassdef, mreadprop, self.location) + self.mreadpropdef = mreadpropdef + modelbuilder.mpropdef2npropdef[mreadpropdef] = self + + var writename = name + "=" + var nwritable = self.n_writable + var mwriteprop = modelbuilder.try_get_mproperty_by_name(nid2, mclassdef, writename).as(nullable MMethod) + var nwkwredef: nullable Token = null + if nwritable != null then nwkwredef = nwritable.n_kwredef + if mwriteprop == null then + var mvisibility + if nwritable != null then + mvisibility = new_property_visibility(modelbuilder, nclassdef, nwritable.n_visibility) + else + mvisibility = private_visibility + end + mwriteprop = new MMethod(mclassdef, writename, mvisibility) + self.check_redef_keyword(modelbuilder, nclassdef, nwkwredef, false, mwriteprop) + else + self.check_redef_keyword(modelbuilder, nclassdef, nwkwredef, true, mwriteprop) + if nwritable != null then + check_redef_property_visibility(modelbuilder, nclassdef, nwritable.n_visibility, mwriteprop) + end + end + var mwritepropdef = new MMethodDef(mclassdef, mwriteprop, self.location) + self.mwritepropdef = mwritepropdef + modelbuilder.mpropdef2npropdef[mwritepropdef] = self + end + end + + redef fun build_signature(modelbuilder, nclassdef) + do + var mpropdef = self.mpropdef + if mpropdef == null then return # Error thus skiped + var mmodule = mpropdef.mclassdef.mmodule + var mtype: nullable MType = null + + var ntype = self.n_type + if ntype != null then + mtype = modelbuilder.resolve_mtype(nclassdef, ntype) + if mtype == null then return + end + + if mtype == null then + modelbuilder.warning(self, "Error: Untyped attribute {mpropdef}") + return + end + + mpropdef.static_mtype = mtype + + var mreadpropdef = self.mreadpropdef + if mreadpropdef != null then + var msignature = new MSignature(new Array[String], new Array[MType], mtype, -1) + mreadpropdef.msignature = msignature + end + + var msritepropdef = self.mwritepropdef + if mwritepropdef != null then + var name: String + if n_id != null then + name = n_id.text.substring_from(1) + else + name = n_id2.text + end + var msignature = new MSignature([name], [mtype], null, -1) + mwritepropdef.msignature = msignature + end + end + + redef fun check_signature(modelbuilder, nclassdef) + do + var mpropdef = self.mpropdef + if mpropdef == null then return # Error thus skiped + var mmodule = mpropdef.mclassdef.mmodule + var ntype = self.n_type + var mtype = self.mpropdef.static_mtype + if mtype == null then return # Error thus skiped + + # Lookup for signature in the precursor + # FIXME all precursors should be considered + if not mpropdef.is_intro then + var precursor_type = mpropdef.mproperty.intro.static_mtype + if precursor_type == null then return + + if mtype != precursor_type then + modelbuilder.error(ntype.as(not null), "Redef Error: Wrong static type. found {mtype}, expected {precursor_type}.") + return + end + end + + # FIXME: Check getter ans setter + end +end + +redef class ATypePropdef + # The associated MVirtualTypeDef once build by a `ModelBuilder' + var mpropdef: nullable MVirtualTypeDef + redef fun build_property(modelbuilder, nclassdef) + do + var mclassdef = nclassdef.mclassdef.as(not null) + var name = self.n_id.text + var mprop = modelbuilder.try_get_mproperty_by_name(self.n_id, mclassdef, name) + if mprop == null then + var mvisibility = new_property_visibility(modelbuilder, nclassdef, self.n_visibility) + mprop = new MVirtualTypeProp(mclassdef, name, mvisibility) + self.check_redef_keyword(modelbuilder, nclassdef, self.n_kwredef, false, mprop) + else + self.check_redef_keyword(modelbuilder, nclassdef, self.n_kwredef, true, mprop) + assert mprop isa MVirtualTypeProp + check_redef_property_visibility(modelbuilder, nclassdef, self.n_visibility, mprop) + end + var mpropdef = new MVirtualTypeDef(mclassdef, mprop, self.location) + self.mpropdef = mpropdef + end + + redef fun build_signature(modelbuilder, nclassdef) + do + var mpropdef = self.mpropdef + if mpropdef == null then return # Error thus skiped + var mmodule = mpropdef.mclassdef.mmodule + var mtype: nullable MType = null + + var ntype = self.n_type + mtype = modelbuilder.resolve_mtype(nclassdef, ntype) + if mtype == null then return + + mpropdef.bound = mtype + # print "{mpropdef}: {mtype}" + end + + redef fun check_signature(modelbuilder, nclassdef) + do + var bound = self.mpropdef.bound + + # Fast case: the bound is not a formal type + if not bound isa MVirtualType then return + + var mmodule = nclassdef.mclassdef.mmodule + var anchor = nclassdef.mclassdef.bound_mtype + + # Slow case: progress on each resolution until: (i) we loop, or (ii) we found a non formal type + var seen = [self.mpropdef.mproperty.mvirtualtype] + loop + if seen.has(bound) then + seen.add(bound) + modelbuilder.error(self, "Error: circularity of virtual type definition: {seen.join(" -> ")}") + return + end + seen.add(bound) + var next = bound.lookup_bound(mmodule, anchor) + if not next isa MVirtualType then return + bound = next + end + end +end diff --git a/src/naiveinterpreter.nit b/src/naiveinterpreter.nit new file mode 100644 index 0000000..cb2e61b --- /dev/null +++ b/src/naiveinterpreter.nit @@ -0,0 +1,1409 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Interpretation of a Nit program directly on the AST +module naiveinterpreter + +import literal +import typing +import auto_super_init + +redef class ModelBuilder + # Execute the program from the entry point (Sys::main) of the `mainmodule' + # `arguments' are the command-line arguments in order + # REQUIRE that: + # 1. the AST is fully loaded. + # 2. the model is fully built. + # 3. the instructions are fully analysed. + fun run_naive_interpreter(mainmodule: MModule, arguments: Array[String]) + do + var time0 = get_time + self.toolcontext.info("*** START INTERPRETING ***", 1) + + var interpreter = new NaiveInterpreter(self, mainmodule, arguments) + var mainclasses = model.get_mclasses_by_name("Sys") + if mainclasses == null then return + assert mainclasses.length == 1 + var mainclass = mainclasses.first + var props = model.get_mproperties_by_name("main") + assert props.length == 1 + var methods = props.first.lookup_definitions(mainmodule, mainclass.mclass_type) + assert methods.length == 1 else print methods.join(", ") + var mainobj = new Instance(mainclass.mclass_type) + interpreter.mainobj = mainobj + interpreter.init_instance(mainobj) + var initprop = try_get_mproperty_by_name2(nmodules.first, mainmodule, mainclass.mclass_type, "init") + if initprop != null then + assert initprop isa MMethod + interpreter.send(initprop, [mainobj]) + end + interpreter.check_init_instance(mainobj) + interpreter.send(interpreter.get_property("main", mainobj), [mainobj]) + + var time1 = get_time + self.toolcontext.info("*** END INTERPRETING: {time1-time0} ***", 2) + end +end + +# The visitor that interprets the Nit Program by walking on the AST +private class NaiveInterpreter + # The modelbuilder that know the AST and its associations with the model + var modelbuilder: ModelBuilder + + # The main moduleof the program (used to lookup methoda + var mainmodule: MModule + + # The command line arguments of the interpreted program + # arguments.first is the program name + # arguments[1] is the first argument + var arguments: Array[String] + + var mainobj: nullable Instance + + init(modelbuilder: ModelBuilder, mainmodule: MModule, arguments: Array[String]) + do + self.modelbuilder = modelbuilder + self.mainmodule = mainmodule + self.arguments = arguments + self.true_instance = new PrimitiveInstance[Bool](get_class("Bool").mclass_type, true) + self.false_instance = new PrimitiveInstance[Bool](get_class("Bool").mclass_type, false) + self.null_instance = new Instance(mainmodule.model.null_type) + end + + # Force to get the primitive class named `name' or abort + fun get_class(name: String): MClass + do + var cla = mainmodule.model.get_mclasses_by_name(name) + if cla == null then + if name == "Bool" then + var c = new MClass(mainmodule, name, 0, enum_kind, public_visibility) + var cladef = new MClassDef(mainmodule, c.mclass_type, new Location(null, 0,0,0,0), new Array[String]) + return c + end + fatal("Fatal Error: no primitive class {name}") + abort + end + assert cla.length == 1 else print cla.join(", ") + return cla.first + end + + # Force to get the primitive property named `name' in the instance `recv' or abort + fun get_property(name: String, recv: Instance): MMethod + do + var props = self.mainmodule.model.get_mproperties_by_name(name) + if props == null then + fatal("Fatal Error: no primitive property {name} on {recv}") + abort + end + var mtype = recv.mtype + var res: nullable MMethod = null + for mprop in props do + assert mprop isa MMethod + if not mtype.has_mproperty(self.mainmodule, mprop) then continue + if res == null then + res = mprop + else + fatal("Fatal Error: ambigous property name '{name}'; conflict between {mprop.full_name} and {res.full_name}") + abort + end + end + if res == null then + fatal("Fatal Error: no primitive property {name} on {recv}") + abort + end + return res + end + + # Subtype test in the context of the mainmodule + fun is_subtype(sub, sup: MType): Bool + do + return sub.is_subtype(self.mainmodule, self.frame.arguments.first.mtype.as(MClassType), sup) + end + + # Is a return executed? + # Set this mark to skip the evaluation until the end of the current method + var returnmark: Bool = false + + # Is a break executed? + # Set this mark to skip the evaluation until a labeled statement catch it with `is_break' + var breakmark: nullable EscapeMark = null + + # Is a continue executed? + # Set this mark to skip the evaluation until a labeled statement catch it with `is_continue' + var continuemark: nullable EscapeMark = null + + # Is a return or a break or a continue executed? + # Use this function to know if you must skip the evaluation of statements + fun is_escaping: Bool do return returnmark or breakmark != null or continuemark != null + + # The value associated with the current return/break/continue, if any. + # Set the value when you set a escapemark. + # Read the value when you catch a mark or reach the end of a method + var escapevalue: nullable Instance = null + + # If there is a break and is associated with `escapemark', then return true an clear the mark. + # If there is no break or if `escapemark' is null then return false. + # Use this function to catch a potential break. + fun is_break(escapemark: nullable EscapeMark): Bool + do + if escapemark != null and self.breakmark == escapemark then + self.breakmark = null + return true + else + return false + end + end + + # If there is a continue and is associated with `escapemark', then return true an clear the mark. + # If there is no continue or if `escapemark' is null then return false. + # Use this function to catch a potential continue. + fun is_continue(escapemark: nullable EscapeMark): Bool + do + if escapemark != null and self.continuemark == escapemark then + self.continuemark = null + return true + else + return false + end + end + + # Evaluate `n' as an expression in the current context. + # Return the value of the expression. + # If `n' cannot be evaluated, then aborts. + fun expr(n: AExpr): Instance + do + var old = self.frame.current_node + self.frame.current_node = n + #n.debug("IN Execute expr") + var i = n.expr(self).as(not null) + #n.debug("OUT Execute expr: value is {i}") + #if not is_subtype(i.mtype, n.mtype.as(not null)) then n.debug("Expected {n.mtype.as(not null)} got {i}") + self.frame.current_node = old + return i + end + + # Evaluate `n' as a statement in the current context. + # Do nothing if `n' is sull. + # If `n' cannot be evaluated, then aborts. + fun stmt(n: nullable AExpr) + do + if n != null then + var old = self.frame.current_node + self.frame.current_node = n + #n.debug("Execute stmt") + n.stmt(self) + self.frame.current_node = old + end + end + + # Map used to store values of nodes that must be evaluated once in the system (AOnceExpr) + var onces: Map[ANode, Instance] = new HashMap[ANode, Instance] + + # Return the boolean instance associated with `val'. + fun bool_instance(val: Bool): Instance + do + if val then return self.true_instance else return self.false_instance + end + + # Return the integer instance associated with `val'. + fun int_instance(val: Int): Instance + do + var ic = get_class("Int") + return new PrimitiveInstance[Int](ic.mclass_type, val) + end + + # Return the char instance associated with `val'. + fun char_instance(val: Char): Instance + do + var ic = get_class("Char") + return new PrimitiveInstance[Char](ic.mclass_type, val) + end + + # Return the float instance associated with `val'. + fun float_instance(val: Float): Instance + do + var ic = get_class("Float") + return new PrimitiveInstance[Float](ic.mclass_type, val) + end + + # The unique intance of the `true' value. + var true_instance: Instance + + # The unique intance of the `false' value. + var false_instance: Instance + + # The unique intance of the `null' value. + var null_instance: Instance + + # Return a new array made of `values'. + # The dynamic type of the result is Array[elttype]. + fun array_instance(values: Array[Instance], elttype: MType): Instance + do + assert not elttype.need_anchor + var nat = new PrimitiveInstance[Array[Instance]](self.get_class("NativeArray").get_mtype([elttype]), values) + var mtype = self.get_class("Array").get_mtype([elttype]) + var res = new Instance(mtype) + self.init_instance(res) + self.send(self.get_property("with_native", res), [res, nat, self.int_instance(values.length)]) + self.check_init_instance(res) + return res + end + + # Return a new native string initialized with `txt' + fun native_string_instance(txt: String): Instance + do + var val = new Buffer.from(txt) + var ic = get_class("NativeString") + return new PrimitiveInstance[Buffer](ic.mclass_type, val) + end + + # The current frame used to store local variables of the current method executed + fun frame: Frame do return frames.first + + # The stack of all frames. The first one is the current one. + var frames: List[Frame] = new List[Frame] + + # Return a stack stace. One line per function + fun stack_trace: String + do + var b = new Buffer + b.append(",---- Stack trace -- - - -\n") + for f in frames do + b.append("| {f.mpropdef} ({f.current_node.location})\n") + end + b.append("`------------------- - - -") + return b.to_s + end + + # Exit the program with a message + fun fatal(message: String) + do + if frames.is_empty then + print message + else + self.frame.current_node.fatal(self, message) + end + exit(1) + end + + # Execute `mpropdef' for a `args' (where args[0] is the receiver). + # Return a falue if `mpropdef' is a function, or null if it is a procedure. + # The call is direct/static. There is no message-seding/late-bindng. + fun call(mpropdef: MMethodDef, args: Array[Instance]): nullable Instance + do + var vararg_rank = mpropdef.msignature.vararg_rank + if vararg_rank >= 0 then + assert args.length >= mpropdef.msignature.arity + 1 # because of self + var rawargs = args + args = new Array[Instance] + + args.add(rawargs.first) # recv + + for i in [0..vararg_rank[ do + args.add(rawargs[i+1]) + end + + var vararg_lastrank = vararg_rank + rawargs.length-1-mpropdef.msignature.arity + var vararg = new Array[Instance] + for i in [vararg_rank..vararg_lastrank] do + vararg.add(rawargs[i+1]) + end + # FIXME: its it to late to determine the vararg type, this should have been done during a previous analysis + var elttype = mpropdef.msignature.parameter_mtypes[vararg_rank].anchor_to(self.mainmodule, args.first.mtype.as(MClassType)) + args.add(self.array_instance(vararg, elttype)) + + for i in [vararg_lastrank+1..rawargs.length-1[ do + args.add(rawargs[i+1]) + end + end + assert args.length == mpropdef.msignature.arity + 1 # because of self + + # Look for the AST node that implements the property + var mproperty = mpropdef.mproperty + if self.modelbuilder.mpropdef2npropdef.has_key(mpropdef) then + var npropdef = self.modelbuilder.mpropdef2npropdef[mpropdef] + return npropdef.call(self, mpropdef, args) + else if mproperty.name == "init" then + var nclassdef = self.modelbuilder.mclassdef2nclassdef[mpropdef.mclassdef] + return nclassdef.call(self, mpropdef, args) + else + fatal("Fatal Error: method {mpropdef} not found in the AST") + abort + end + end + + # Execute `mproperty' for a `args' (where args[0] is the receiver). + # Return a falue if `mproperty' is a function, or null if it is a procedure. + # The call is polimotphic. There is a message-seding/late-bindng according to te receiver (args[0]). + fun send(mproperty: MMethod, args: Array[Instance]): nullable Instance + do + var recv = args.first + var mtype = recv.mtype + if mtype isa MNullType then + if mproperty.name == "==" then + return self.bool_instance(args[0] == args[1]) + else if mproperty.name == "!=" then + return self.bool_instance(args[0] != args[1]) + end + #fatal("Reciever is null. {mproperty}. {args.join(" ")} {self.frame.current_node.class_name}") + fatal("Reciever is null") + abort + end + var propdefs = mproperty.lookup_definitions(self.mainmodule, mtype) + if propdefs.length > 1 then + fatal("NOT YET IMPLEMETED ERROR: Property conflict: {propdefs.join(", ")}") + abort + end + assert propdefs.length == 1 else + fatal("Fatal Error: No property '{mproperty}' for '{recv}'") + abort + end + var propdef = propdefs.first + return self.call(propdef, args) + end + + # Read the attribute `mproperty' of an instance `recv' and return its value. + # If the attribute in not yet initialized, then aborts with an error message. + fun read_attribute(mproperty: MAttribute, recv: Instance): Instance + do + if not recv.attributes.has_key(mproperty) then + fatal("Uninitialized attribute {mproperty.name}") + abort + end + return recv.attributes[mproperty] + end + + # Fill the initial values of the newly created instance `recv'. + # `recv.mtype' is used to know what must be filled. + fun init_instance(recv: Instance) + do + for cd in recv.mtype.collect_mclassdefs(self.mainmodule) + do + var n = self.modelbuilder.mclassdef2nclassdef[cd] + for npropdef in n.n_propdefs do + if npropdef isa AAttrPropdef then + npropdef.init_expr(self, recv) + end + end + end + end + + # Check that non nullable attributes of `recv' are correctly initialized. + # This function is used as the last instruction of a new + # FIXME: this will work better once there is nullable types + fun check_init_instance(recv: Instance) + do + for cd in recv.mtype.collect_mclassdefs(self.mainmodule) + do + var n = self.modelbuilder.mclassdef2nclassdef[cd] + for npropdef in n.n_propdefs do + if npropdef isa AAttrPropdef and npropdef.n_expr == null then + # Force read to check the initialization + self.read_attribute(npropdef.mpropdef.mproperty, recv) + end + end + end + end + + # This function determine the correct type according the reciever of the current definition (self). + fun unanchor_type(mtype: MType): MType + do + return mtype.anchor_to(self.mainmodule, self.frame.arguments.first.mtype.as(MClassType)) + end +end + +# An instance represents a value of the executed program. +class Instance + # The dynamic type of the instance + # ASSERT: not self.mtype.is_anchored + var mtype: MType + + # The values of the attributes + var attributes: Map[MAttribute, Instance] = new HashMap[MAttribute, Instance] + + # return true if the instance is the true value. + # return false if the instance is the true value. + # else aborts + fun is_true: Bool do abort + + # Return true if `self' IS `o' (using the Nit semantic of is) + fun eq_is(o: Instance): Bool do return self is o + + # Human readable object identity "Type#number" + redef fun to_s do return "{mtype}#{object_id}" + + # Return the integer valur is the instance is an integer. + # else aborts + fun to_i: Int do abort + + # The real value encapsulated if the instance is primitive. + # Else aborts. + fun val: Object do abort +end + +# Special instance to handle primitives values (int, bool, etc.) +# The trick it just to encapsulate the <> value +class PrimitiveInstance[E: Object] + super Instance + + # The real value encapsulated + redef var val: E + + init(mtype: MType, val: E) + do + super(mtype) + self.val = val + end + + redef fun is_true + do + if val == true then return true + if val == false then return false + abort + end + + redef fun ==(o) + do + if not o isa PrimitiveInstance[Object] then return false + return self.val == o.val + end + + redef fun eq_is(o) + do + if not o isa PrimitiveInstance[Object] then return false + return self.val is o.val + end + + redef fun to_s do return "{mtype}#{val.object_id}({val})" + + redef fun to_i do return val.as(Int) +end + +# Information about local variables in a running method +private class Frame + # The current visited node + # The node is stored by frame to keep a stack trace + var current_node: ANode + # The executed property. + # A Method in case of a call, an attribute in case of a default initialization. + var mpropdef: MPropDef + # Arguments of the method (the first is te receiver + var arguments: Array[Instance] + # Mapping betwen a variable an the current value + var map: Map[Variable, Instance] = new HashMap[Variable, Instance] +end + +redef class ANode + # Aborts the program with a message + # `v' is used to know if a colored message is displayed or not + private fun fatal(v: NaiveInterpreter, message: String) + do + if v.modelbuilder.toolcontext.opt_no_color.value == true then + print("{message} ({location.file.filename}:{location.line_start})") + else + print("{location}: {message}\n{location.colored_line("0;31")}") + print(v.stack_trace) + end + exit(1) + end +end + +redef class APropdef + # Execute a `mpropdef' associated with the current node. + private fun call(v: NaiveInterpreter, mpropdef: MMethodDef, args: Array[Instance]): nullable Instance + do + fatal(v, "Unimplemented {mpropdef}") + abort + end +end + +redef class AConcreteMethPropdef + redef fun call(v, mpropdef, args) + do + var f = new Frame(self, self.mpropdef.as(not null), args) + for i in [0..mpropdef.msignature.arity[ do + var variable = self.n_signature.n_params[i].variable + assert variable != null + f.map[variable] = args[i+1] + end + + v.frames.unshift(f) + + # Call the implicit super-init + var auto_super_inits = self.auto_super_inits + if auto_super_inits != null then + var selfarg = [args.first] + for auto_super_init in auto_super_inits do + if auto_super_init.intro.msignature.arity == 0 then + v.send(auto_super_init, selfarg) + else + v.send(auto_super_init, args) + end + end + end + + v.stmt(self.n_block) + v.frames.shift + v.returnmark = false + var res = v.escapevalue + v.escapevalue = null + return res + end +end + +redef class AInternMethPropdef + redef fun call(v, mpropdef, args) + do + var pname = mpropdef.mproperty.name + var cname = mpropdef.mclassdef.mclass.name + if pname == "output" then + var recv = args.first + recv.val.output + return null + else if pname == "object_id" then + var recv = args.first + if recv isa PrimitiveInstance[Object] then + return v.int_instance(recv.val.object_id) + else + return v.int_instance(recv.object_id) + end + else if pname == "output_class_name" then + var recv = args.first + print recv.mtype.as(MClassType).mclass + return null + else if pname == "native_class_name" then + var recv = args.first + var txt = recv.mtype.as(MClassType).mclass.to_s + return v.native_string_instance(txt) + else if pname == "==" then + # == is correclt redefined for instances + return v.bool_instance(args[0] == args[1]) + else if pname == "!=" then + return v.bool_instance(args[0] != args[1]) + else if pname == "is_same_type" then + return v.bool_instance(args[0].mtype == args[1].mtype) + else if pname == "exit" then + exit(args[1].to_i) + abort + else if pname == "sys" then + return v.mainobj + else if cname == "Int" then + if pname == "unary -" then + return v.int_instance(-args[0].to_i) + else if pname == "succ" then + return v.int_instance(args[0].to_i + 1) + else if pname == "prec" then + return v.int_instance(args[0].to_i - 1) + else if pname == "+" then + return v.int_instance(args[0].to_i + args[1].to_i) + else if pname == "-" then + return v.int_instance(args[0].to_i - args[1].to_i) + else if pname == "*" then + return v.int_instance(args[0].to_i * args[1].to_i) + else if pname == "%" then + return v.int_instance(args[0].to_i % args[1].to_i) + else if pname == "/" then + return v.int_instance(args[0].to_i / args[1].to_i) + else if pname == "<" then + return v.bool_instance(args[0].to_i < args[1].to_i) + else if pname == ">" then + return v.bool_instance(args[0].to_i > args[1].to_i) + else if pname == "<=" then + return v.bool_instance(args[0].to_i <= args[1].to_i) + else if pname == ">=" then + return v.bool_instance(args[0].to_i >= args[1].to_i) + else if pname == "<=>" then + return v.int_instance(args[0].to_i <=> args[1].to_i) + else if pname == "ascii" then + return v.char_instance(args[0].to_i.ascii) + else if pname == "to_f" then + return v.float_instance(args[0].to_i.to_f) + else if pname == "lshift" then + return v.int_instance(args[0].to_i.lshift(args[1].to_i)) + else if pname == "rshift" then + return v.int_instance(args[0].to_i.rshift(args[1].to_i)) + end + else if cname == "Char" then + var recv = args[0].val.as(Char) + if pname == "ascii" then + return v.int_instance(recv.ascii) + else if pname == "succ" then + return v.char_instance(recv.succ) + else if pname == "prec" then + return v.char_instance(recv.prec) + else if pname == "<" then + return v.bool_instance(recv < args[1].val.as(Char)) + else if pname == ">" then + return v.bool_instance(recv > args[1].val.as(Char)) + else if pname == "<=" then + return v.bool_instance(recv <= args[1].val.as(Char)) + else if pname == ">=" then + return v.bool_instance(recv >= args[1].val.as(Char)) + else if pname == "<=>" then + return v.int_instance(recv <=> args[1].val.as(Char)) + end + else if cname == "Float" then + if pname == "+" then + return v.float_instance(args[0].val.as(Float) + args[1].val.as(Float)) + else if pname == "-" then + return v.float_instance(args[0].val.as(Float) - args[1].val.as(Float)) + else if pname == "*" then + return v.float_instance(args[0].val.as(Float) * args[1].val.as(Float)) + else if pname == "/" then + return v.float_instance(args[0].val.as(Float) / args[1].val.as(Float)) + else if pname == "to_i" then + return v.int_instance(args[0].val.as(Float).to_i) + end + else if cname == "NativeString" then + var recvval = args.first.val.as(Buffer) + if pname == "[]" then + return v.char_instance(recvval[args[1].to_i]) + else if pname == "[]=" then + recvval[args[1].to_i] = args[2].val.as(Char) + return null + else if pname == "copy_to" then + # sig= copy_to(dest: NativeString, length: Int, from: Int, to: Int) + recvval.copy(args[3].to_i, args[2].to_i, args[1].val.as(Buffer), args[4].to_i) + return null + else if pname == "atoi" then + return v.int_instance(recvval.to_i) + end + else if pname == "calloc_string" then + return v.native_string_instance("!" * args[1].to_i) + else if cname == "NativeArray" then + var recvval = args.first.val.as(Array[Instance]) + if pname == "[]" then + if args[1].to_i >= recvval.length then + debug("Illegal access on {recvval} for element {args[1].to_i}/{recvval.length}") + end + return recvval[args[1].to_i] + else if pname == "[]=" then + recvval[args[1].to_i] = args[2] + return null + else if pname == "copy_to" then + recvval.copy(0, args[2].to_i, args[1].val.as(Array[Instance]), 0) + return null + end + else if pname == "calloc_array" then + var recvtype = args.first.mtype.as(MClassType) + var mtype: MType = recvtype.supertype_to(v.mainmodule, recvtype, v.get_class("ArrayCapable")) + mtype = mtype.as(MGenericType).arguments.first + var val = new Array[Instance].filled_with(v.null_instance, args[1].to_i) + return new PrimitiveInstance[Array[Instance]](v.get_class("NativeArray").get_mtype([mtype]), val) + end + fatal(v, "Unimplemented intern {mpropdef}") + abort + end +end + +redef class AbstractArray[E] + fun copy(start: Int, len: Int, dest: AbstractArray[E], new_start: Int) + do + self.copy_to(start, len, dest, new_start) + end +end + +redef class AExternInitPropdef + redef fun call(v, mpropdef, args) + do + var pname = mpropdef.mproperty.name + var cname = mpropdef.mclassdef.mclass.name + if pname == "native_stdout" then + return new PrimitiveInstance[OStream](mpropdef.mclassdef.mclass.mclass_type, stdout) + else if pname == "native_stdin" then + return new PrimitiveInstance[IStream](mpropdef.mclassdef.mclass.mclass_type, stdin) + else if pname == "native_stderr" then + return new PrimitiveInstance[OStream](mpropdef.mclassdef.mclass.mclass_type, stderr) + else if pname == "io_open_read" then + var a1 = args[1].val.as(Buffer) + return new PrimitiveInstance[IStream](mpropdef.mclassdef.mclass.mclass_type, new IFStream.open(a1.to_s)) + else if pname == "io_open_write" then + var a1 = args[1].val.as(Buffer) + return new PrimitiveInstance[OStream](mpropdef.mclassdef.mclass.mclass_type, new OFStream.open(a1.to_s)) + end + fatal(v, "Unimplemented extern init {mpropdef}") + abort + end +end + +redef class AExternMethPropdef + super TablesCapable + redef fun call(v, mpropdef, args) + do + var pname = mpropdef.mproperty.name + var cname = mpropdef.mclassdef.mclass.name + if cname == "NativeFile" then + var recvval = args.first.val + if pname == "io_write" then + var a1 = args[1].val.as(Buffer) + recvval.as(OStream).write(a1.substring(0, args[2].to_i)) + return args[2] + else if pname == "io_read" then + var str = recvval.as(IStream).read(args[2].to_i) + var a1 = args[1].val.as(Buffer) + new Buffer.from(str).copy(0, str.length, a1, 0) + return v.int_instance(str.length) + else if pname == "io_close" then + recvval.as(IOS).close + return v.int_instance(0) + end + else if cname == "NativeString" then + var recvval = args.first.val.as(Buffer) + if pname == "file_exists" then + return v.bool_instance(recvval.to_s.file_exists) + else if pname == "file_mkdir" then + recvval.to_s.mkdir + return null + else if pname == "get_environ" then + var txt = args.first.val.as(Buffer).to_s.to_symbol.environ + return v.native_string_instance(txt) + end + else if pname == "native_argc" then + return v.int_instance(v.arguments.length) + else if pname == "native_argv" then + var txt = v.arguments[args[1].to_i] + return v.native_string_instance(txt) + else if pname == "get_time" then + return v.int_instance(get_time) + else if pname == "lexer_goto" then + return v.int_instance(lexer_goto(args[1].to_i, args[2].to_i)) + else if pname == "lexer_accept" then + return v.int_instance(lexer_accept(args[1].to_i)) + else if pname == "parser_goto" then + return v.int_instance(parser_goto(args[1].to_i, args[2].to_i)) + else if pname == "parser_action" then + return v.int_instance(parser_action(args[1].to_i, args[2].to_i)) + end + fatal(v, "Unimplemented extern {mpropdef}") + abort + end +end + +redef class AAttrPropdef + redef fun call(v, mpropdef, args) + do + var attr = self.mpropdef.mproperty + if args.length == 1 then + return v.read_attribute(attr, args.first) + else + assert args.length == 2 + args.first.attributes[attr] = args[1] + return null + end + end + + # Evaluate and set the default value of the attribute in `recv' + private fun init_expr(v: NaiveInterpreter, recv: Instance) + do + var nexpr = self.n_expr + if nexpr != null then + var f = new Frame(self, self.mpropdef.as(not null), [recv]) + v.frames.unshift(f) + var val = v.expr(nexpr) + v.frames.shift + assert not v.is_escaping + recv.attributes[self.mpropdef.mproperty] = val + return + end + var mtype = self.mpropdef.static_mtype.as(not null) + # TODO The needinit info is statically computed, move it to modelbuilder or whatever + mtype = mtype.resolve_for(self.mpropdef.mclassdef.bound_mtype, self.mpropdef.mclassdef.bound_mtype, self.mpropdef.mclassdef.mmodule, true) + if mtype isa MNullableType then + recv.attributes[self.mpropdef.mproperty] = v.null_instance + end + end +end + +redef class AClassdef + # Execute an implicit `mpropdef' associated with the current node. + private fun call(v: NaiveInterpreter, mpropdef: MMethodDef, args: Array[Instance]): nullable Instance + do + var super_inits = self.super_inits + if super_inits != null then + assert args.length == 1 + for su in super_inits do + v.send(su, args) + end + return null + end + var recv = args.first + var i = 1 + # Collect undefined attributes + for npropdef in self.n_propdefs do + if npropdef isa AAttrPropdef and npropdef.n_expr == null then + recv.attributes[npropdef.mpropdef.mproperty] = args[i] + i += 1 + end + end + return null + end +end + +redef class AExpr + # Evaluate the node as a possible expression. + # Return a possible value + # NOTE: Do not call this method directly, but use `v.expr' + # This method is here to be implemented by subclasses. + private fun expr(v: NaiveInterpreter): nullable Instance + do + fatal(v, "Unimplemented expr {class_name}") + abort + end + + # Evaluate the node as a statement. + # NOTE: Do not call this method directly, but use `v.stmt' + # This method is here to be implemented by subclasses (no need to return something). + private fun stmt(v: NaiveInterpreter) + do + expr(v) + end + +end + +redef class ABlockExpr + redef fun stmt(v) + do + for e in self.n_expr do + v.stmt(e) + if v.is_escaping then return + end + end +end + +redef class AVardeclExpr + redef fun stmt(v) + do + var ne = self.n_expr + if ne != null then + var i = v.expr(ne) + v.frame.map[self.variable.as(not null)] = i + end + end +end + +redef class AVarExpr + redef fun expr(v) + do + return v.frame.map[self.variable.as(not null)] + end +end + +redef class AVarAssignExpr + redef fun stmt(v) + do + var i = v.expr(self.n_value) + v.frame.map[self.variable.as(not null)] = i + end +end + +redef class AVarReassignExpr + redef fun stmt(v) + do + var vari = v.frame.map[self.variable.as(not null)] + var value = v.expr(self.n_value) + var res = v.send(reassign_property.mproperty, [vari, value]) + assert res != null + v.frame.map[self.variable.as(not null)] = res + end +end + +redef class ASelfExpr + redef fun expr(v) + do + return v.frame.arguments.first + end +end + +redef class AContinueExpr + redef fun stmt(v) + do + v.continuemark = self.escapemark + end +end + +redef class ABreakExpr + redef fun stmt(v) + do + v.breakmark = self.escapemark + end +end + +redef class AReturnExpr + redef fun stmt(v) + do + var ne = self.n_expr + if ne != null then + var i = v.expr(ne) + v.escapevalue = i + end + v.returnmark = true + end +end + +redef class AAbortExpr + redef fun stmt(v) + do + fatal(v, "Aborted") + exit(1) + end +end + +redef class AIfExpr + redef fun stmt(v) + do + var cond = v.expr(self.n_expr) + if cond.is_true then + v.stmt(self.n_then) + else + v.stmt(self.n_else) + end + end +end + +redef class AIfexprExpr + redef fun expr(v) + do + var cond = v.expr(self.n_expr) + if cond.is_true then + return v.expr(self.n_then) + else + return v.expr(self.n_else) + end + end +end + +redef class ADoExpr + redef fun stmt(v) + do + v.stmt(self.n_block) + v.is_break(self.escapemark) # Clear the break (if any) + end +end + +redef class AWhileExpr + redef fun stmt(v) + do + loop + var cond = v.expr(self.n_expr) + if not cond.is_true then return + v.stmt(self.n_block) + if v.is_break(self.escapemark) then return + v.is_continue(self.escapemark) # Clear the break + if v.is_escaping then return + end + end +end + +redef class ALoopExpr + redef fun stmt(v) + do + loop + v.stmt(self.n_block) + if v.is_break(self.escapemark) then return + v.is_continue(self.escapemark) # Clear the break + if v.is_escaping then return + end + end +end + +redef class AForExpr + redef fun stmt(v) + do + var col = v.expr(self.n_expr) + #self.debug("col {col}") + var iter = v.send(v.get_property("iterator", col), [col]).as(not null) + #self.debug("iter {iter}") + loop + var isok = v.send(v.get_property("is_ok", iter), [iter]).as(not null) + if not isok.is_true then return + var item = v.send(v.get_property("item", iter), [iter]).as(not null) + #self.debug("item {item}") + v.frame.map[self.variables.first] = item + v.stmt(self.n_block) + if v.is_break(self.escapemark) then return + v.is_continue(self.escapemark) # Clear the break + if v.is_escaping then return + v.send(v.get_property("next", iter), [iter]) + end + end +end + +redef class AAssertExpr + redef fun stmt(v) + do + var cond = v.expr(self.n_expr) + if not cond.is_true then + v.stmt(self.n_else) + if v.is_escaping then return + var nid = self.n_id + if nid != null then + fatal(v, "Assert '{nid.text}' failed") + else + fatal(v, "Assert failed") + end + exit(1) + end + end +end + +redef class AOrExpr + redef fun expr(v) + do + var cond = v.expr(self.n_expr) + if cond.is_true then return cond + return v.expr(self.n_expr2) + end +end + +redef class AAndExpr + redef fun expr(v) + do + var cond = v.expr(self.n_expr) + if not cond.is_true then return cond + return v.expr(self.n_expr2) + end +end + +redef class ANotExpr + redef fun expr(v) + do + var cond = v.expr(self.n_expr) + return v.bool_instance(not cond.is_true) + end +end + +redef class AOrElseExpr + redef fun expr(v) + do + var i = v.expr(self.n_expr) + if i != v.null_instance then return i + return v.expr(self.n_expr2) + end +end + +redef class AEeExpr + redef fun expr(v) + do + var i = v.expr(self.n_expr) + var i2 = v.expr(self.n_expr2) + return v.bool_instance(i.eq_is(i2)) + end +end + +redef class AIntExpr + redef fun expr(v) + do + return v.int_instance(self.value.as(not null)) + end +end + +redef class AFloatExpr + redef fun expr(v) + do + return v.float_instance(self.value.as(not null)) + end +end + +redef class ACharExpr + redef fun expr(v) + do + return v.char_instance(self.value.as(not null)) + end +end + +redef class AArrayExpr + redef fun expr(v) + do + var val = new Array[Instance] + for nexpr in self.n_exprs.n_exprs do + val.add(v.expr(nexpr)) + end + var mtype = v.unanchor_type(self.mtype.as(not null)).as(MGenericType) + var elttype = mtype.arguments.first + return v.array_instance(val, elttype) + end +end + +redef class AStringFormExpr + redef fun expr(v) + do + var txt = self.value.as(not null) + var nat = v.native_string_instance(txt) + var res = new Instance(v.get_class("String").mclass_type) + v.init_instance(res) + v.send(v.get_property("from_cstring", res), [res, nat]) + v.check_init_instance(res) + return res + end +end + +redef class ASuperstringExpr + redef fun expr(v) + do + var array = new Array[Instance] + for nexpr in n_exprs do + array.add(v.expr(nexpr)) + end + var i = v.array_instance(array, v.get_class("Object").mclass_type) + var res = v.send(v.get_property("to_s", i), [i]) + assert res != null + return res + end +end + +redef class ACrangeExpr + redef fun expr(v) + do + var e1 = v.expr(self.n_expr) + var e2 = v.expr(self.n_expr2) + var mtype = v.unanchor_type(self.mtype.as(not null)) + var res = new Instance(mtype) + v.init_instance(res) + v.send(v.get_property("init", res), [res, e1, e2]) + v.check_init_instance(res) + return res + end +end + +redef class AOrangeExpr + redef fun expr(v) + do + var e1 = v.expr(self.n_expr) + var e2 = v.expr(self.n_expr2) + var mtype = v.unanchor_type(self.mtype.as(not null)) + var res = new Instance(mtype) + v.init_instance(res) + v.send(v.get_property("without_last", res), [res, e1, e2]) + v.check_init_instance(res) + return res + end +end + +redef class ATrueExpr + redef fun expr(v) + do + return v.bool_instance(true) + end +end + +redef class AFalseExpr + redef fun expr(v) + do + return v.bool_instance(false) + end +end + +redef class ANullExpr + redef fun expr(v) + do + return v.null_instance + end +end + +redef class AIsaExpr + redef fun expr(v) + do + var i = v.expr(self.n_expr) + var mtype = v.unanchor_type(self.cast_type.as(not null)) + return v.bool_instance(v.is_subtype(i.mtype, mtype)) + end +end + +redef class AAsCastExpr + redef fun expr(v) + do + var i = v.expr(self.n_expr) + var mtype = v.unanchor_type(self.mtype.as(not null)) + if not v.is_subtype(i.mtype, mtype) then + #fatal(v, "Cast failed expected {mtype}, got {i}") + fatal(v, "Cast failed") + end + return i + end +end + +redef class AAsNotnullExpr + redef fun expr(v) + do + var i = v.expr(self.n_expr) + var mtype = v.unanchor_type(self.mtype.as(not null)) + if i.mtype isa MNullType then + fatal(v, "Cast failed") + end + return i + end +end + +redef class AParExpr + redef fun expr(v) + do + return v.expr(self.n_expr) + end +end + +redef class AOnceExpr + redef fun expr(v) + do + if v.onces.has_key(self) then + return v.onces[self] + else + var res = v.expr(self.n_expr) + v.onces[self] = res + return res + end + end +end + +redef class ASendExpr + redef fun expr(v) + do + var recv = v.expr(self.n_expr) + var args = [recv] + for a in compute_raw_arguments do + args.add(v.expr(a)) + end + var mproperty = self.mproperty.as(not null) + return v.send(mproperty, args) + end +end + +redef class ASendReassignFormExpr + redef fun stmt(v) + do + var recv = v.expr(self.n_expr) + var args = [recv] + for a in compute_raw_arguments do + args.add(v.expr(a)) + end + var value = v.expr(self.n_value) + + var mproperty = self.mproperty.as(not null) + var read = v.send(mproperty, args) + assert read != null + + var write = v.send(self.reassign_property.mproperty, [read, value]) + assert write != null + + args.add(write) + + v.send(self.write_mproperty.as(not null), args) + end +end + +redef class ASuperExpr + redef fun expr(v) + do + var recv = v.frame.arguments.first + var args = [recv] + for a in self.n_args.n_exprs do + args.add(v.expr(a)) + end + if args.length == 1 then + args = v.frame.arguments + end + + var mproperty = self.mproperty + if mproperty != null then + if mproperty.intro.msignature.arity == 0 then + args = [recv] + end + # Super init call + var res = v.send(mproperty, args) + return res + end + + # stantard call-next-method + var mpropdef = v.frame.mpropdef + # FIXME: we do not want an ugly static call! + var mpropdefs = mpropdef.mproperty.lookup_super_definitions(mpropdef.mclassdef.mmodule, mpropdef.mclassdef.bound_mtype) + if mpropdefs.length != 1 then + debug("MPRODFEFS for super {mpropdef} for {recv}: {mpropdefs.join(", ")}") + end + mpropdef = mpropdefs.first + assert mpropdef isa MMethodDef + var res = v.call(mpropdef, args) + return res + end +end + +redef class ANewExpr + redef fun expr(v) + do + var mtype = v.unanchor_type(self.mtype.as(not null)) + var recv = new Instance(mtype) + v.init_instance(recv) + var args = [recv] + for a in self.n_args.n_exprs do + args.add(v.expr(a)) + end + var mproperty = self.mproperty.as(not null) + var res2 = v.send(mproperty, args) + if res2 != null then + #self.debug("got {res2} from {mproperty}. drop {recv}") + return res2 + end + v.check_init_instance(recv) + return recv + end +end + +redef class AAttrExpr + redef fun expr(v) + do + var recv = v.expr(self.n_expr) + var mproperty = self.mproperty.as(not null) + return v.read_attribute(mproperty, recv) + end +end + +redef class AAttrAssignExpr + redef fun stmt(v) + do + var recv = v.expr(self.n_expr) + var i = v.expr(self.n_value) + var mproperty = self.mproperty.as(not null) + recv.attributes[mproperty] = i + end +end + +redef class AAttrReassignExpr + redef fun stmt(v) + do + var recv = v.expr(self.n_expr) + var value = v.expr(self.n_value) + var mproperty = self.mproperty.as(not null) + var attr = v.read_attribute(mproperty, recv) + var res = v.send(reassign_property.mproperty, [attr, value]) + assert res != null + recv.attributes[mproperty] = res + end +end + +redef class AIssetAttrExpr + redef fun expr(v) + do + var recv = v.expr(self.n_expr) + var mproperty = self.mproperty.as(not null) + return v.bool_instance(recv.attributes.has_key(mproperty)) + end +end + +redef class ADebugTypeExpr + redef fun stmt(v) + do + # do nothing + end +end diff --git a/src/nit.nit b/src/nit.nit new file mode 100644 index 0000000..5fbefd5 --- /dev/null +++ b/src/nit.nit @@ -0,0 +1,53 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# A naive Nit interpreter +module nit + +import modelbuilder +import exprbuilder +import naiveinterpreter + +# Create a tool context to handle options and paths +var toolcontext = new ToolContext +# Add an option "-o" to enable compatibilit with the tests.sh script +var opt = new OptionString("compatibility (does noting)", "-o") +toolcontext.option_context.add_option(opt) +# We do not add other options, so process them now! +toolcontext.process_options + +# We need a model to collect stufs +var model = new Model +# An a model builder to parse files +var modelbuilder = new ModelBuilder(model, toolcontext) + +var arguments = toolcontext.option_context.rest +if arguments.is_empty then + toolcontext.option_context.usage + return +end +var progname = arguments.first + +# Here we load an process all modules passed on the command line +var mmodules = modelbuilder.parse_and_build([progname]) +modelbuilder.full_propdef_semantic_analysis + +if toolcontext.opt_only_metamodel.value then exit(0) + +# Here we launch the interpreter on the main module +assert mmodules.length == 1 +var mainmodule = mmodules.first +modelbuilder.run_naive_interpreter(mainmodule, arguments) diff --git a/src/nitstats.nit b/src/nitstats.nit new file mode 100644 index 0000000..24bafd2 --- /dev/null +++ b/src/nitstats.nit @@ -0,0 +1,577 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Program that collect various data about nit programs and libraries +module nitstats + +import modelbuilder +import exprbuilder +import runtime_type + +# The job of this visitor is to resolve all types found +class ATypeCounterVisitor + super Visitor + var modelbuilder: ModelBuilder + var nclassdef: AClassdef + + var typecount: HashMap[MType, Int] + var total: Int = 0 + + # Get a new visitor on a classef to add type count in `typecount'. + init(modelbuilder: ModelBuilder, nclassdef: AClassdef, typecount: HashMap[MType, Int]) + do + self.modelbuilder = modelbuilder + self.nclassdef = nclassdef + self.typecount = typecount + end + + redef fun visit(n) + do + if n isa AType then + var mtype = modelbuilder.resolve_mtype(self.nclassdef, n) + if mtype != null then + self.total += 1 + if self.typecount.has_key(mtype) then + self.typecount[mtype] += 1 + else + self.typecount[mtype] = 1 + end + if not mtype.need_anchor then + var cldefs = mtype.collect_mclassdefs(nclassdef.mclassdef.mmodule) + end + end + end + n.visit_all(self) + end +end + +class ANewVisitor + super Visitor + var modelbuilder: ModelBuilder + var nclassdef: AClassdef + + var news: Set[MClass] + + # Get a new visitor on a classef to add type count in `typecount'. + init(modelbuilder: ModelBuilder, nclassdef: AClassdef, news: Set[MClass]) + do + self.modelbuilder = modelbuilder + self.nclassdef = nclassdef + self.news = news + end + + redef fun visit(n) + do + if n isa ANewExpr then + var mtype = modelbuilder.resolve_mtype(self.nclassdef, n.n_type) + if mtype != null then + assert mtype isa MClassType + self.news.add(mtype.mclass) + end + end + n.visit_all(self) + end +end + +# Visit all `nmodules' of a modelbuilder and compute statistics on the usage of explicit static types +fun count_ntypes(modelbuilder: ModelBuilder) +do + # Count each occurence of a specific static type + var typecount = new HashMap[MType, Int] + # Total number of explicit static types + var total = 0 + + # Visit all the source code to collect data + for nmodule in modelbuilder.nmodules do + for nclassdef in nmodule.n_classdefs do + var visitor = new ATypeCounterVisitor(modelbuilder, nclassdef, typecount) + visitor.enter_visit(nclassdef) + total += visitor.total + end + end + + # Display data + print "--- Statistics of the explitic static types ---" + print "Total number of explicit static types: {total}" + if total == 0 then return + + # types sorted by usage + var types = typecount.keys.to_a + types.sort !cmp a, b = typecount[a] <=> typecount[b] + + # Display most used types (ie the last of `types') + print "Most used types: " + var min = 10 + if types.length < min then min = types.length + for i in [0..min[ do + var t = types[types.length-i-1] + print " {t}: {typecount[t]}" + end + + # Compute the distribution of type usage + print "Distribution of type usage:" + var count = 0 + var sum = 0 + var limit = 1 + for t in types do + if typecount[t] > limit then + print " <={limit}: {count} ({div(count*100,types.length)}% of types; {div(sum*100,total)}% of usage)" + count = 0 + sum = 0 + while typecount[t] > limit do limit = limit * 2 + end + count += 1 + sum += typecount[t] + end + print " <={limit}: {count} ({div(count*100,types.length)}% of types; {div(sum*100,total)}% of usage)" +end + +fun visit_news(modelbuilder: ModelBuilder, mainmodule: MModule) +do + print "--- Dead classes ---" + # Count each occurence of a specific static type + var news = new HashSet[MClass] + + # Visit all the source code to collect data + for nmodule in modelbuilder.nmodules do + for nclassdef in nmodule.n_classdefs do + var visitor = new ANewVisitor(modelbuilder, nclassdef, news) + visitor.enter_visit(nclassdef) + end + end + + for c in modelbuilder.model.mclasses do + if c.kind == concrete_kind and not news.has(c) then + print "{c.full_name}" + end + end + + var hier = mainmodule.flatten_mclass_hierarchy + for c in hier do + if c.kind != abstract_kind and not (c.kind == concrete_kind and not news.has(c)) then continue + + for sup in hier[c].greaters do + for cd in sup.mclassdefs do + for p in cd.intro_mproperties do + if p isa MAttribute then + continue label classes + end + end + end + end + print "no attributes: {c.full_name}" + + end label classes +end + +# Compute general statistics on a model +fun compute_statistics(model: Model) +do + print "--- Statistics of the model ---" + var nbmod = model.mmodules.length + print "Number of modules: {nbmod}" + + print "" + + var nbcla = model.mclasses.length + var nbcladef = model.mclassdef_hierarchy.length + print "Number of classes: {nbcla}" + + # determine the distribution of: + # * class kinds (interface, abstract class, etc.) + # * refinex classes (vs. unrefined ones) + var kinds = new HashMap[MClassKind, Int] + var refined = 0 + for c in model.mclasses do + if kinds.has_key(c.kind) then + kinds[c.kind] += 1 + else + kinds[c.kind] = 1 + end + if c.mclassdefs.length > 1 then + refined += 1 + end + end + for k,v in kinds do + print " Number of {k} kind: {v} ({div(v*100,nbcla)}%)" + end + + + print "" + + print "Nomber of class definitions: {nbcladef}" + print "Number of refined classes: {refined} ({div(refined*100,nbcla)}%)" + print "Average number of class refinments by classes: {div(nbcladef-nbcla,nbcla)}" + print "Average number of class refinments by refined classes: {div(nbcladef-nbcla,refined)}" + + print "" + + var nbprop = model.mproperties.length + print "Number of properties: {model.mproperties.length}" +end + +# Compute class tables for the classes of the program main +fun compute_tables(main: MModule) +do + var model = main.model + + var nc = 0 # Number of runtime classes + var nl = 0 # Number of usages of class definitions (a class definition can be used more than once) + var nhp = 0 # Number of usages of properties (a property can be used more than once) + var npas = 0 # Number of usages of properties without lookup (easy easy case, easier that CHA) + + # Collect the full class hierarchy + var hier = main.flatten_mclass_hierarchy + for c in hier do + # Skip classes without direct instances + if c.kind == interface_kind or c.kind == abstract_kind then continue + + nc += 1 + + # Now, we need to collect all properties defined/inherited/imported + # So, visit all definitions of all super-classes + for sup in hier[c].greaters do + for cd in sup.mclassdefs do + nl += 1 + + # Now, search properties introduced + for p in cd.intro_mproperties do + + nhp += 1 + # Select property definition + if p.mpropdefs.length == 1 then + npas += 1 + else + var sels = p.lookup_definitions(main, c.mclassdefs.first.bound_mtype) + if sels.length > 1 then + print "conflict for {p.full_name} in class {c.full_name}: {sels.join(", ")}" + else if sels.is_empty then + print "ERROR: no property for {p.full_name} in class {c.full_name}!" + end + end + end + end + end + end + + print "--- Construction of tables ---" + print "Number of runtime classes: {nc} (excluding interfaces and abstract classes)" + print "Average number of composing class definition by runtime class: {div(nl,nc)}" + print "Total size of tables (classes and instances): {nhp} (not including stuff like info for subtyping or call-next-method)" + print "Average size of table by runtime class: {div(nhp,nc)}" + print "Values never redefined: {npas} ({div(npas*100,nhp)}%)" +end + +# Helper function to display n/d and handle division by 0 +fun div(n: Int, d: Int): String +do + if d == 0 then return "na" + return ((100*n/d).to_f/100.0).to_precision(2) +end + +# Create a dot file representing the module hierarchy of a model. +# Importation relation is represented with arrow +# Nesting relation is represented with nested boxes +fun generate_module_hierarchy(model: Model) +do + var buf = new Buffer + buf.append("digraph \{\n") + buf.append("node [shape=box];\n") + buf.append("rankdir=BT;\n") + for mmodule in model.mmodules do + if mmodule.direct_owner == null then + generate_module_hierarchy_for(mmodule, buf) + end + end + for mmodule in model.mmodules do + for s in mmodule.in_importation.direct_greaters do + buf.append("\"{mmodule}\" -> \"{s}\";\n") + end + end + buf.append("\}\n") + var f = new OFStream.open("module_hierarchy.dot") + f.write(buf.to_s) + f.close +end + +# Helper function for `generate_module_hierarchy'. +# Create graphviz nodes for the module and recusrively for its nested modules +private fun generate_module_hierarchy_for(mmodule: MModule, buf: Buffer) +do + if mmodule.in_nesting.direct_greaters.is_empty then + buf.append("\"{mmodule.name}\";\n") + else + buf.append("subgraph \"cluster_{mmodule.name}\" \{label=\"\"\n") + buf.append("\"{mmodule.name}\";\n") + for s in mmodule.in_nesting.direct_greaters do + generate_module_hierarchy_for(s, buf) + end + buf.append("\}\n") + end +end + +# Create a dot file representing the class hierarchy of a model. +fun generate_class_hierarchy(mmodule: MModule) +do + var buf = new Buffer + buf.append("digraph \{\n") + buf.append("node [shape=box];\n") + buf.append("rankdir=BT;\n") + var hierarchy = mmodule.flatten_mclass_hierarchy + for mclass in hierarchy do + buf.append("\"{mclass}\" [label=\"{mclass}\"];\n") + for s in hierarchy[mclass].direct_greaters do + buf.append("\"{mclass}\" -> \"{s}\";\n") + end + end + buf.append("\}\n") + var f = new OFStream.open("class_hierarchy.dot") + f.write(buf.to_s) + f.close +end + +# Create a dot file representing the classdef hierarchy of a model. +# For a simple user of the model, the classdef hierarchy is not really usefull, it is more an internal thing. +fun generate_classdef_hierarchy(model: Model) +do + var buf = new Buffer + buf.append("digraph \{\n") + buf.append("node [shape=box];\n") + buf.append("rankdir=BT;\n") + for mmodule in model.mmodules do + for mclassdef in mmodule.mclassdefs do + buf.append("\"{mclassdef} {mclassdef.bound_mtype}\" [label=\"{mclassdef.mmodule}\\n{mclassdef.bound_mtype}\"];\n") + for s in mclassdef.in_hierarchy.direct_greaters do + buf.append("\"{mclassdef} {mclassdef.bound_mtype}\" -> \"{s} {s.bound_mtype}\";\n") + end + end + end + buf.append("\}\n") + var f = new OFStream.open("classdef_hierarchy.dot") + f.write(buf.to_s) + f.close +end + +fun generate_model_hyperdoc(model: Model) +do + var buf = new Buffer + buf.append("\n\n") + buf.append("

Model

\n") + + buf.append("

Modules

\n") + for mmodule in model.mmodules do + buf.append("

{mmodule}

\n") + buf.append("
\n") + buf.append("
direct owner
\n") + var own = mmodule.direct_owner + if own != null then buf.append("
{linkto(own)}
\n") + buf.append("
nested
\n") + for x in mmodule.in_nesting.direct_greaters do + buf.append("
{linkto(x)}
\n") + end + buf.append("
direct import
\n") + for x in mmodule.in_importation.direct_greaters do + buf.append("
{linkto(x)}
\n") + end + buf.append("
direct clients
\n") + for x in mmodule.in_importation.direct_smallers do + buf.append("
{linkto(x)}
\n") + end + buf.append("
introduced classes
\n") + for x in mmodule.mclassdefs do + if not x.is_intro then continue + buf.append("
{linkto(x.mclass)} by {linkto(x)}
\n") + end + buf.append("
refined classes
\n") + for x in mmodule.mclassdefs do + if x.is_intro then continue + buf.append("
{linkto(x.mclass)} by {linkto(x)}
\n") + end + buf.append("
\n") + end + buf.append("

Classes

\n") + for mclass in model.mclasses do + buf.append("

{mclass}

\n") + buf.append("
\n") + buf.append("
module of introduction
\n") + buf.append("
{linkto(mclass.intro_mmodule)}
\n") + buf.append("
class definitions
\n") + for x in mclass.mclassdefs do + buf.append("
{linkto(x)} in {linkto(x.mmodule)}
\n") + end + buf.append("
\n") + end + buf.append("

Class Definitions

\n") + for mclass in model.mclasses do + for mclassdef in mclass.mclassdefs do + buf.append("

{mclassdef}

\n") + buf.append("
\n") + buf.append("
module
\n") + buf.append("
{linkto(mclassdef.mmodule)}
\n") + buf.append("
class
\n") + buf.append("
{linkto(mclassdef.mclass)}
\n") + buf.append("
direct refinements
\n") + for x in mclassdef.in_hierarchy.direct_greaters do + if x.mclass != mclass then continue + buf.append("
{linkto(x)} in {linkto(x.mmodule)}
\n") + end + buf.append("
direct refinemees
\n") + for x in mclassdef.in_hierarchy.direct_smallers do + if x.mclass != mclass then continue + buf.append("
{linkto(x)} in {linkto(x.mmodule)}
\n") + end + buf.append("
direct superclasses
\n") + for x in mclassdef.supertypes do + buf.append("
{linkto(x.mclass)} by {x}
\n") + end + buf.append("
introduced properties
\n") + for x in mclassdef.mpropdefs do + if not x.is_intro then continue + buf.append("
{linkto(x.mproperty)} by {linkto(x)}
\n") + end + buf.append("
redefined properties
\n") + for x in mclassdef.mpropdefs do + if x.is_intro then continue + buf.append("
{linkto(x.mproperty)} by {linkto(x)}
\n") + end + buf.append("
\n") + end + end + buf.append("

Properties

\n") + for mprop in model.mproperties do + buf.append("

{mprop}

\n") + buf.append("
\n") + buf.append("
module of introdcution
\n") + buf.append("
{linkto(mprop.intro_mclassdef.mmodule)}
\n") + buf.append("
class of introduction
\n") + buf.append("
{linkto(mprop.intro_mclassdef.mclass)}
\n") + buf.append("
class definition of introduction
\n") + buf.append("
{linkto(mprop.intro_mclassdef)}
\n") + buf.append("
property definitions
\n") + for x in mprop.mpropdefs do + buf.append("
{linkto(x)} in {linkto(x.mclassdef)}
\n") + end + buf.append("
\n") + end + buf.append("

Property Definitions

\n") + for mprop in model.mproperties do + for mpropdef in mprop.mpropdefs do + buf.append("

{mpropdef}

\n") + buf.append("
\n") + buf.append("
module
\n") + buf.append("
{linkto(mpropdef.mclassdef.mmodule)}
\n") + buf.append("
class
\n") + buf.append("
{linkto(mpropdef.mclassdef.mclass)}
\n") + buf.append("
class definition
\n") + buf.append("
{linkto(mpropdef.mclassdef)}
\n") + buf.append("
super definitions
\n") + for x in mpropdef.mproperty.lookup_super_definitions(mpropdef.mclassdef.mmodule, mpropdef.mclassdef.bound_mtype) do + buf.append("
{linkto(x)} in {linkto(x.mclassdef)}
\n") + end + end + end + buf.append("\n") + var f = new OFStream.open("model.html") + f.write(buf.to_s) + f.close +end + +fun linkto(o: Object): String +do + if o isa MModule then + return "{o}" + else if o isa MClass then + return "{o}" + else if o isa MClassDef then + return "{o}" + else if o isa MProperty then + return "{o}" + else if o isa MPropDef then + return "{o}" + else + print "cannot linkto {o.class_name}" + abort + end +end + +fun runtime_type(modelbuilder: ModelBuilder, mainmodule: MModule) +do + var analysis = modelbuilder.do_runtime_type(mainmodule) + + print "--- Type Analysis ---" + print "Number of live runtime types (instantied resolved type): {analysis.live_types.length}" + print "Number of live polymorphic method: {analysis.polymorphic_methods.length}" + print "Number of live method definitions: {analysis.live_methoddefs.length}" + print "Number of live runtime method definitions (with customization): {analysis.runtime_methods.length}" + print "Number of live runtime cast types (ie used in as and isa): {analysis.live_cast_types.length}" + + for mprop in modelbuilder.model.mproperties do + if not mprop isa MMethod then continue + if analysis.polymorphic_methods.has(mprop) then continue + for methoddef in mprop.mpropdefs do + if analysis.live_methoddefs.has(methoddef) then continue label l + end + #print " {mprop.full_name} is dead" + end label l +end + +# Create a tool context to handle options and paths +var toolcontext = new ToolContext +# We do not add other options, so process them now! +toolcontext.process_options + +# We need a model to collect stufs +var model = new Model +# An a model builder to parse files +var modelbuilder = new ModelBuilder(model, toolcontext) + +# Here we load an process all modules passed on the command line +var mmodules = modelbuilder.parse_and_build(toolcontext.option_context.rest) + +if mmodules.length == 0 then return + +var mainmodule: MModule +if mmodules.length == 1 then + mainmodule = mmodules.first +else + # We need a main module, so we build it by importing all modules + mainmodule = new MModule(model, null, "
", new Location(null, 0, 0, 0, 0)) + mainmodule.set_imported_mmodules(mmodules) +end + +# Now, we just have to play with the model! +print "*** STATS ***" + +print "" +compute_statistics(model) + +print "" +#visit_news(modelbuilder, mainmodule) + +print "" +count_ntypes(modelbuilder) + +generate_module_hierarchy(model) +generate_classdef_hierarchy(model) +generate_class_hierarchy(mainmodule) +generate_model_hyperdoc(model) + +print "" +compute_tables(mainmodule) + +print "" +modelbuilder.full_propdef_semantic_analysis +runtime_type(modelbuilder, mainmodule) diff --git a/src/parser/parser.nit b/src/parser/parser.nit index daeb288..11222e5 100644 --- a/src/parser/parser.nit +++ b/src/parser/parser.nit @@ -3,6 +3,7 @@ package parser intrude import parser_prod +import tables # State of the parser automata as stored in the parser stack. private class State diff --git a/src/parser/xss/main.xss b/src/parser/xss/main.xss index ba1360b..d6bd9e8 100644 --- a/src/parser/xss/main.xss +++ b/src/parser/xss/main.xss @@ -71,6 +71,7 @@ $ output 'parser.nit' package parser intrude import parser_prod +import tables $ call make_parser() $ end output diff --git a/src/poset.nit b/src/poset.nit new file mode 100644 index 0000000..99f5bde --- /dev/null +++ b/src/poset.nit @@ -0,0 +1,223 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Pre order sets and partial order set (ie hierarchies) +module poset + +# Preorder set graph. +# This class modelize an incremental preorder graph where new node and edges can be added (but no removal) +# Preorder graph has two caracteristics: +# * reflexivity: an element is in relation with itself (ie `self.has(e)' implies `self.has_edge(e,e)') +# * transitivity: `self.has_edge(e,f)' and `self.has_edge(f,g)' implies `self.has_edge(e,g)' +class POSet[E: Object] + super NaiveCollection[E] + + redef fun iterator do return nodes.iterator + + # All the nodes + private var nodes: Set[E] = new HashSet[E] + private var tos: HashMap[E, Set[E]] = new HashMap[E, Set[E]] + private var froms: HashMap[E, Set[E]] = new HashMap[E, Set[E]] + private var dtos: HashMap[E, Set[E]] = new HashMap[E, Set[E]] + private var dfroms: HashMap[E, Set[E]] = new HashMap[E, Set[E]] + private var elements: HashMap[E, POSetElement[E]] = new HashMap[E, POSetElement[E]] + + # Add a node (an element) to the posed + # The new element is added unconnected to any other nodes (it is both a new root and a new leaf). + # Return the POSetElement associated to `e'. + # If `e' is already present in the POSet then just return the POSetElement (usually you will prefer []) is this case. + fun add_node(e: E): POSetElement[E] + do + if nodes.has(e) then return self.elements[e] + nodes.add(e) + tos[e] = new HashSet[E] + tos[e].add(e) + froms[e] = new HashSet[E] + froms[e].add(e) + dtos[e] = new HashSet[E] + dfroms[e] = new HashSet[E] + var poe = new POSetElement[E](self, e, nodes.length) + self.elements[e] = poe + return poe + end + + # Return a view of `e' in the poset. + # This allows to asks manipulate elements in thier relation with others elements. + # + # var poset = POSet[Something] = ... + # for x in poset do + # for y in poset[x].direct_greaters do + # print "{x} -> {y}" + # end + # end + # + # REQUIRE: has(e) + fun [](e: E): POSetElement[E] + do + assert nodes.has(e) + return self.elements[e] + end + + # Add an edge from `f' to `t'. + # Because a POSet is transitive, all transitive edges are also added to the graph. + # If the edge already exists, the this function does nothing. + # If a reverse edge (from `t' to 'f') already exists, a loop is created. + # + # FIXME: Do somethind clever to manage loops. + fun add_edge(f, t: E) + do + add_node(f) + add_node(t) + # Skip if edge already present + if tos[f].has(t) then return + # Add the edge and close the transitivity + for ff in froms[f] do + for tt in tos[t] do + froms[tt].add ff + tos[ff].add tt + end + end + # Update the transitive reduction + if tos[t].has(f) then return # Skip the reduction if there is a loop + + for x in dfroms[t].to_a do + if tos[x].has(f) then + dfroms[t].remove(x) + dtos[x].remove(t) + end + end + for x in dtos[f].to_a do + if froms[x].has(t) then + dfroms[x].remove(f) + dtos[f].remove(x) + end + end + dtos[f].add t + dfroms[t].add f + end + + # Is there an edge (transitive or not) from `f' to `t'? + # Since the POSet is reflexive, true is returned if `f == t'. + fun has_edge(f,t: E): Bool + do + return nodes.has(f) and tos[f].has(t) + end + + # Is there a direct edge from `f' to `t'? + # Note that because of loops, the result may not be the expected one. + fun has_direct_edge(f,t: E): Bool + do + return nodes.has(f) and dtos[f].has(t) + end + + # Display the POSet in a gaphical windows. + # Graphviz with a working -Txlib is expected. + # Used fo debugging. + fun show_dot + do + var f = new OProcess("dot", "-Txlib") + #var f = stdout + f.write "digraph \{\n" + for x in nodes do + for y in dtos[x] do + if self.has_edge(y,x) then + f.write "\"{x}\" -> \"{y}\"[dir=both];\n" + else + f.write "\"{x}\" -> \"{y}\";\n" + end + end + end + f.write "\}\n" + #f.close + #f.wait + end + + # Compare two elements in an arbitrary total order. + # Tis function is mainly used to sort elements of the set in an arbitrary linear extension. + # if ab then return 1 + # if a == b then return 0 + # else return -1 or 1 + # The total order is stable unless a new node or a new edge is added + fun compare(a, b: E): Int + do + var res = tos[a].length <=> tos[b].length + if res != 0 then return res + return elements[a].count <=> elements[b].count + end +end + +# View of an objet in a poset +# This class is a helper to handle specific queries on a same object +# +# For instance, one common usage is to add a specific attribute for each poset a class belong. +# +# class Thing +# var in_some_relation: POSetElement[Thing] +# var in_other_relation: POSetElement[Thing] +# end +# var t: Thing ... +# t.in_some_relation.greaters +# +class POSetElement[E: Object] + # The poset self belong to + var poset: POSet[E] + + # The real object behind the view + var element: E + + # The rank of the + # This attribute is used to force a total order for POSet#compare + private var count: Int + + # Return the set of all elements `t' that have an edge from `element' to `t'. + # Since the POSet is reflexive, element is included in the set. + fun greaters: Collection[E] + do + return self.poset.tos[self.element] + end + + # Return the set of all elements `t' that have a direct edge from `element' to `t'. + fun direct_greaters: Collection[E] + do + return self.poset.dtos[self.element] + end + + # Return the set of all elements `f' that have an edge from `f' to `element'. + # Since the POSet is reflexive, element is included in the set. + fun smallers: Collection[E] + do + return self.poset.froms[self.element] + end + + # Return the set of all elements `f' that have an edge from `f' to `element'. + fun direct_smallers: Collection[E] + do + return self.poset.dfroms[self.element] + end + + # Is there an edge from `object' to `t'? + fun <=(t: E): Bool + do + return self.poset.tos[self.element].has(t) + end + + # Is `t != element' and is there an edge from `object' to `t'? + fun <(t: E): Bool + do + return t != self.element and self.poset.tos[self.element].has(t) + end +end diff --git a/src/runtime_type.nit b/src/runtime_type.nit new file mode 100644 index 0000000..2616edf --- /dev/null +++ b/src/runtime_type.nit @@ -0,0 +1,561 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + + +# Rapid type analysis on the AST with heterogenous generics and customization +# +# Rapid type analysis is an analyse that aproximates the set of live classes +# and the set of live methods starting from the entry point of the program. +# These two sets are interdependant and computed together. +# It is quite efficient but the type set is global such pollute each call site. +# +# Heterogenous generics means that each intancied generic class is associated +# to a distinct runtime type. +# Heterogenous generics has the advantage to resolve the the formal generic +# parameters types but increase the number of types. +# More important, heterogenous generics cannot deal with infinite number of runtime +# types since the analyse tries to list them all (so some programs will be badly refused) +# +# Customization means that each method definition is analyzed one per runtime +# type of receiver. +# Customization have the following advantages: +# * `self' is monomorphic +# * virtual types are all resolved +# * live attributes can be determined on each class +# But the big disavantage to explode the number of runtime method: each method +# definition for each runtime type that need it +module runtime_type + +import model +import modelbuilder +import typing +import auto_super_init + +redef class MModule + var main_type: nullable MClassType + var main_init: nullable MMethod + var main_method: nullable MMethod +end + +redef class ModelBuilder + fun do_runtime_type(mainmodule: MModule): RuntimeTypeAnalysis + do + var model = self.model + var analysis = new RuntimeTypeAnalysis(self, mainmodule) + var nmodule = self.nmodules.first + var mainclass = self.try_get_mclass_by_name(nmodule, mainmodule, "Sys") + assert mainclass != null + var props = model.get_mproperties_by_name("main") + assert props.length == 1 + var methods = props.first.lookup_definitions(mainmodule, mainclass.mclass_type) + assert methods.length == 1 else print methods.join(", ") + var maintype = mainclass.mclass_type + analysis.add_type(maintype) + mainmodule.main_type = maintype + var initprop = self.try_get_mproperty_by_name2(nmodule, mainmodule, maintype, "init") + if initprop != null then + assert initprop isa MMethod + analysis.add_monomorphic_send(maintype, initprop) + end + mainmodule.main_init = initprop + var mainprop = self.try_get_mproperty_by_name2(nmodule, mainmodule, maintype, "main") + if mainprop != null then + assert mainprop isa MMethod + analysis.add_monomorphic_send(maintype, mainprop) + end + mainmodule.main_method = mainprop + analysis.run_analysis + return analysis + end +end + +class RuntimeTypeAnalysis + var modelbuilder: ModelBuilder + var mainmodule: MModule + var live_types: HashSet[MClassType] = new HashSet[MClassType] + var live_cast_types: HashSet[MClassType] = new HashSet[MClassType] + var polymorphic_methods: HashSet[MMethod] = new HashSet[MMethod] + var live_methoddefs: HashSet[MMethodDef] = new HashSet[MMethodDef] + var runtime_methods: HashSet[RuntimeMethod] = new HashSet[RuntimeMethod] + var live_send_site: HashSet[RuntimeSendSite] = new HashSet[RuntimeSendSite] + + private var todo: List[RuntimeMethod] = new List[RuntimeMethod] + + fun add_type(mtype: MClassType) + do + if self.live_types.has(mtype) then return + + assert not mtype.need_anchor + self.live_types.add(mtype) + + for rss in self.live_send_site do + if not mtype.is_subtype(self.mainmodule, null, rss.receiver) then continue + if mtype.has_mproperty(self.mainmodule, rss.mmethod) then + self.add_monomorphic_send(mtype, rss.mmethod) + end + end + end + + fun add_send(mtype: MClassType, mmethod: MMethod) + do + var rss = new RuntimeSendSite(mmethod, mtype) + if self.live_send_site.has(rss) then return + + self.live_send_site.add(rss) + self.polymorphic_methods.add(mmethod) + + for mtype2 in self.live_types do + if not mtype2.is_subtype(self.mainmodule, null, mtype) then continue + if mtype2.has_mproperty(self.mainmodule, mmethod) then + self.add_monomorphic_send(mtype2, mmethod) + end + end + end + + fun add_monomorphic_send(mtype: MClassType, mmethod: MMethod) + do + assert self.live_types.has(mtype) + var defs = mmethod.lookup_definitions(self.mainmodule, mtype) + if defs.is_empty then return + assert defs.length == 1 else print "conflict on {mtype} for {mmethod}: {defs.join(" ")}" + self.add_static_call(mtype, defs.first) + end + + fun add_static_call(mtype: MClassType, mmethoddef: MMethodDef) + do + assert self.live_types.has(mtype) + var rm = new RuntimeMethod(mmethoddef, mtype) + if self.runtime_methods.has(rm) then return + self.runtime_methods.add(rm) + self.todo.add(rm) + self.live_methoddefs.add(mmethoddef) + end + + fun add_cast_type(mtype: MClassType) + do + if self.live_cast_types.has(mtype) then return + + assert not mtype.need_anchor + self.live_cast_types.add(mtype) + end + + fun run_analysis + do + while not todo.is_empty do + var mr = todo.shift + if not self.modelbuilder.mpropdef2npropdef.has_key(mr.mmethoddef) then + # It is an init for a class? + if mr.mmethoddef.mproperty.name == "init" then + var nclassdef = self.modelbuilder.mclassdef2nclassdef[mr.mmethoddef.mclassdef] + var super_inits = nclassdef.super_inits + if super_inits != null then + #assert args.length == 1 + for su in super_inits do + self.add_monomorphic_send(mr.receiver, su) + end + end + + else + abort + end + continue + end + var npropdef = self.modelbuilder.mpropdef2npropdef[mr.mmethoddef] + if npropdef isa AConcreteMethPropdef then + #npropdef.debug("Visit {mr.mmethoddef} for {mr.receiver}") + var nclassdef = npropdef.parent.as(AClassdef) + var mmethoddef = npropdef.mpropdef.as(not null) + var auto_super_inits = npropdef.auto_super_inits + if auto_super_inits != null then + for auto_super_init in auto_super_inits do + self.add_monomorphic_send(mr.receiver, auto_super_init) + end + end + var v = new RuntimeTypeVisitor(self, nclassdef, mmethoddef, mr.receiver) + v.enter_visit(npropdef.n_block) + else if npropdef isa ADeferredMethPropdef then + # nothing to do (maybe add a waring?) + else if npropdef isa AAttrPropdef then + # nothing to do + else if npropdef isa AInternMethPropdef or npropdef isa AExternMethPropdef then + # UGLY: We force the "instantation" of the concrete return type if any + var ret = mr.mmethoddef.msignature.return_mtype + if ret != null and ret isa MClassType and ret.mclass.kind != abstract_kind and ret.mclass.kind != interface_kind then + ret = ret.anchor_to(self.mainmodule, mr.receiver) + self.add_type(ret) + end + else if npropdef isa AExternInitPropdef then + self.add_type(mr.receiver) + else + npropdef.debug("Not yet implemented") + abort + end + end + end +end + +class RuntimeMethod + var mmethoddef: MMethodDef + var receiver: MClassType + + redef fun ==(o) + do + return o isa RuntimeMethod and o.mmethoddef == self.mmethoddef and o.receiver == self.receiver + end + + redef fun hash + do + return self.mmethoddef.hash + self.receiver.hash + end +end + +class RuntimeSendSite + var mmethod: MMethod + var receiver: MClassType + + redef fun ==(o) + do + return o isa RuntimeSendSite and o.mmethod == self.mmethod and o.receiver == self.receiver + end + + redef fun hash + do + return self.mmethod.hash + self.receiver.hash + end +end + +private class RuntimeTypeVisitor + super Visitor + + var analysis: RuntimeTypeAnalysis + + var nclassdef: AClassdef + + var mmethoddef: MMethodDef + + var receiver: MClassType + + init(analysis: RuntimeTypeAnalysis, nclassdef: AClassdef, mmethoddef: MMethodDef, receiver: MClassType) + do + self.analysis = analysis + self.nclassdef = nclassdef + self.mmethoddef = mmethoddef + self.receiver = receiver + end + + # Adapt and remove nullable + # return null if we got the null type + fun cleanup_type(mtype: MType): nullable MClassType + do + mtype = mtype.anchor_to(self.analysis.mainmodule, self.receiver) + if mtype isa MNullType then return null + if mtype isa MNullableType then mtype = mtype.mtype + assert mtype isa MClassType + assert not mtype.need_anchor + return mtype + end + + fun add_type(mtype: MType) + do + var runtimetype = cleanup_type(mtype) + if runtimetype == null then return # we do not care about null + + self.analysis.add_type(runtimetype) + #self.current_node.debug("add_type {runtimetype}") + end + + fun add_send(mtype: MType, mproperty: MMethod) + do + var runtimetype = cleanup_type(mtype) + if runtimetype == null then return # we do not care about null + + analysis.add_send(runtimetype, mproperty) + #self.current_node.debug("add_send {mproperty}") + end + + fun add_monomorphic_send(mtype: MType, mproperty: MMethod) + do + var runtimetype = cleanup_type(mtype) + if runtimetype == null then return # we do not care about null + + self.analysis.add_monomorphic_send(runtimetype, mproperty) + #self.current_node.debug("add_static call {runtimetype} {mproperty}") + end + + fun add_cast_type(mtype: MType) + do + var runtimetype = cleanup_type(mtype) + if runtimetype == null then return # we do not care about null + + self.analysis.add_cast_type(runtimetype) + #self.current_node.debug("add_cast_type {runtimetype}") + end + + redef fun visit(node) + do + if node == null then return + node.accept_runtime_type_vistor(self) + node.visit_all(self) + end + + # Force to get the primitive class named `name' or abort + fun get_class(name: String): MClass + do + var cla = analysis.mainmodule.model.get_mclasses_by_name(name) + if cla == null then + if name == "Bool" then + var c = new MClass(analysis.mainmodule, name, 0, enum_kind, public_visibility) + var cladef = new MClassDef(analysis.mainmodule, c.mclass_type, new Location(null, 0,0,0,0), new Array[String]) + return c + end + self.current_node.debug("Fatal Error: no primitive class {name}") + abort + end + assert cla.length == 1 else print cla.join(", ") + return cla.first + end + + # Force to get the primitive property named `name' in the instance `recv' or abort + fun get_method(recv: MType, name: String): MMethod + do + var runtimetype = cleanup_type(recv) + if runtimetype == null then abort + + var props = self.analysis.mainmodule.model.get_mproperties_by_name(name) + if props == null then + self.current_node.debug("Fatal Error: no primitive property {name} on {runtimetype}") + abort + end + var res: nullable MMethod = null + for mprop in props do + assert mprop isa MMethod + if not runtimetype.has_mproperty(self.analysis.mainmodule, mprop) then continue + if mprop.is_init and mprop.intro_mclassdef.mclass != runtimetype.mclass then continue + if res == null then + res = mprop + else + self.current_node.debug("Fatal Error: ambigous property name '{name}'; conflict between {mprop.full_name} and {res.full_name}") + abort + end + end + if res == null then + self.current_node.debug("Fatal Error: no primitive property {name} on {runtimetype}") + abort + end + return res + end +end + +### + +redef class ANode + private fun accept_runtime_type_vistor(v: RuntimeTypeVisitor) + do + end +end + +redef class AIntExpr + redef fun accept_runtime_type_vistor(v) + do + v.add_type(self.mtype.as(not null)) + end +end + +redef class AFloatExpr + redef fun accept_runtime_type_vistor(v) + do + v.add_type(self.mtype.as(not null)) + end +end + +redef class ACharExpr + redef fun accept_runtime_type_vistor(v) + do + v.add_type(self.mtype.as(not null)) + end +end + +redef class AArrayExpr + redef fun accept_runtime_type_vistor(v) + do + var mtype = self.mtype.as(not null) + v.add_type(mtype) + var native = v.get_class("NativeArray").get_mtype([mtype.as(MGenericType).arguments.first]) + v.add_type(native) + var prop = v.get_method(mtype, "with_native") + v.add_monomorphic_send(mtype, prop) + end +end + +redef class AStringFormExpr + redef fun accept_runtime_type_vistor(v) + do + var mtype = self.mtype.as(not null) + v.add_type(mtype) + var native = v.get_class("NativeString").mclass_type + v.add_type(native) + var prop = v.get_method(mtype, "from_cstring") + v.add_monomorphic_send(mtype, prop) + end +end + +redef class ASuperstringExpr + redef fun accept_runtime_type_vistor(v) + do + var arraytype = v.get_class("Array").get_mtype([v.get_class("Object").mclass_type]) + v.add_type(arraytype) + var prop = v.get_method(arraytype, "join") + v.add_monomorphic_send(arraytype, prop) + end +end + +redef class ACrangeExpr + redef fun accept_runtime_type_vistor(v) + do + var mtype = self.mtype.as(not null) + v.add_type(mtype) + var prop = v.get_method(mtype, "init") + v.add_monomorphic_send(mtype, prop) + end +end + +redef class AOrangeExpr + redef fun accept_runtime_type_vistor(v) + do + var mtype = self.mtype.as(not null) + v.add_type(mtype) + var prop = v.get_method(mtype, "without_last") + v.add_monomorphic_send(mtype, prop) + end +end + +redef class ATrueExpr + redef fun accept_runtime_type_vistor(v) + do + v.add_type(self.mtype.as(not null)) + end +end + +redef class AFalseExpr + redef fun accept_runtime_type_vistor(v) + do + v.add_type(self.mtype.as(not null)) + end +end + +redef class AIsaExpr + redef fun accept_runtime_type_vistor(v) + do + v.add_cast_type(self.cast_type.as(not null)) + end +end + +redef class AAsCastExpr + redef fun accept_runtime_type_vistor(v) + do + v.add_cast_type(self.mtype.as(not null)) + end +end + +# + +redef class ASendExpr + redef fun accept_runtime_type_vistor(v) + do + var mproperty = self.mproperty.as(not null) + if n_expr isa ASelfExpr then + v.add_monomorphic_send(v.receiver, mproperty) + else + var recvtype = self.n_expr.mtype.as(not null) + v.add_send(recvtype, mproperty) + end + end +end + +redef class ASendReassignFormExpr + redef fun accept_runtime_type_vistor(v) + do + v.add_send(self.read_type.as(not null), self.reassign_property.mproperty) + var mproperty = self.mproperty.as(not null) + var write_mproperty = self.write_mproperty.as(not null) + if n_expr isa ASelfExpr then + v.add_monomorphic_send(v.receiver, mproperty) + v.add_monomorphic_send(v.receiver, write_mproperty) + else + var recvtype = self.n_expr.mtype.as(not null) + v.add_send(recvtype, mproperty) + v.add_send(recvtype, write_mproperty) + end + end +end + +redef class AVarReassignExpr + redef fun accept_runtime_type_vistor(v) + do + v.add_send(self.read_type.as(not null), self.reassign_property.mproperty) + end +end + +redef class AAttrReassignExpr + redef fun accept_runtime_type_vistor(v) + do + v.add_send(self.read_type.as(not null), self.reassign_property.mproperty) + end +end + +redef class ASuperExpr + redef fun accept_runtime_type_vistor(v) + do + var mproperty = self.mproperty + if mproperty != null then + v.add_monomorphic_send(v.receiver, mproperty) + return + end + + #FIXME: we do not want an ugly static call! + var mpropdef = v.mmethoddef + var mpropdefs = mpropdef.mproperty.lookup_super_definitions(mpropdef.mclassdef.mmodule, mpropdef.mclassdef.bound_mtype) + if mpropdefs.length != 1 then + debug("MPRODFEFS for super {mpropdef} for {v.receiver}: {mpropdefs.join(", ")}") + end + var msuperpropdef = mpropdefs.first + assert msuperpropdef isa MMethodDef + v.analysis.add_static_call(v.receiver, msuperpropdef) + end +end + +redef class AForExpr + redef fun accept_runtime_type_vistor(v) + do + var recvtype = self.n_expr.mtype.as(not null) + var colltype = v.get_class("Collection").mclassdefs.first.bound_mtype + v.add_send(recvtype, v.get_method(colltype, "iterator")) + var iteratortype = v.get_class("Iterator").mclassdefs.first.bound_mtype + var objtype = v.get_class("Object").mclass_type + v.add_send(objtype, v.get_method(iteratortype, "is_ok")) + v.add_send(objtype, v.get_method(iteratortype, "item")) + v.add_send(objtype, v.get_method(iteratortype, "next")) + end +end + +redef class ANewExpr + redef fun accept_runtime_type_vistor(v) + do + var recvtype = self.mtype.as(not null) + v.add_type(recvtype) + v.add_monomorphic_send(recvtype, mproperty.as(not null)) + end +end diff --git a/src/scope.nit b/src/scope.nit new file mode 100644 index 0000000..8914b31 --- /dev/null +++ b/src/scope.nit @@ -0,0 +1,448 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Identification and scping of local variables and labels. +module scope + +import parser +import toolcontext + +# A local variable (including parameters, automatic variables and self) +class Variable + # The name of the variable (as used in the program) + var name: String + + # Alias of `name' + redef fun to_s do return self.name +end + +# A local variable associated to a closure definition +class ClosureVariable + super Variable +end + +# Mark where break and continue will branch. +# marks are either associated with a label of with a for_loop structure +class EscapeMark + # The name of the label (unless the mark is an anonymous loop mark) + var name: nullable String + + # Is the mark atached to a loop (loop, while, for, closure) + # Such a mark is a candidate to a labelless 'continue' or 'break' + var for_loop: Bool + + # Each 'continue' attached to the mark + var continues: Array[AContinueExpr] = new Array[AContinueExpr] + + # Each 'break' attached to the mark + var breaks: Array[ABreakExpr] = new Array[ABreakExpr] +end + +# Visit a npropdef and: +# * Identify variables, closures and labels +# * Associate each break and continue to its escapemark +# * Transform ACallFormExpr that access a variable into AVarFormExpr +# * Transform ACallFormExpr that call a closure into AClosureCallExpr +# FIXME: Should the class be private? +private class ScopeVisitor + super Visitor + + # The tool context used to display errors + var toolcontext: ToolContext + + init(toolcontext: ToolContext) + do + self.toolcontext = toolcontext + scopes.add(new Scope) + end + + # All stacked scope. `scopes.first' is the current scope + private var scopes: List[Scope] = new List[Scope] + + # Regiter a local variable. + # Display an error on toolcontext if a variable with the same name is masked. + fun register_variable(node: ANode, variable: Variable): Bool + do + var name = variable.name + var found = search_variable(name) + if found != null then + self.error(node, "Error: A variable named `{name}' already exists") + return false + end + scopes.first.variables[name] = variable + return true + end + + # Look for a variable named `name'. + # Return null if no such a variable is found. + fun search_variable(name: String): nullable Variable + do + for scope in scopes do + var res = scope.get_variable(name) + if res != null then + return res + end + end + return null + end + + redef fun visit(n: nullable ANode) + do + n.accept_scope_visitor(self) + end + + # Enter in a statement block `node' as inside a new scope. + # The block can be optionally attached to an `escapemark'. + private fun enter_visit_block(node: nullable AExpr, escapemark: nullable EscapeMark) + do + if node == null then return + var scope = new Scope + scope.escapemark = escapemark + scopes.unshift(scope) + enter_visit(node) + scopes.shift + end + + # Look for a label `name'. + # Return nulll if no such a label is found. + private fun search_label(name: String): nullable EscapeMark + do + for scope in scopes do + var res = scope.escapemark + if res != null and res.name == name then + return res + end + end + return null + end + + # Create a new escape mark (possibly with a label) + # Display an error on toolcontext if a label with the same name is masked. + private fun make_escape_mark(nlabel: nullable ALabel, for_loop: Bool): EscapeMark + do + assert named_or_for_loop: nlabel != null or for_loop + var name: nullable String + if nlabel != null then + name = nlabel.n_id.text + var found = self.search_label(name) + if found != null then + self.error(nlabel, "Syntax error: label {name} already defined.") + end + else + name = null + end + var res = new EscapeMark(name, for_loop) + return res + end + + # Look for an escape mark optionally associated with a label. + # If a label is given, the the escapemark of this label is returned. + # If there is no label, the nearest escapemark that is `for loop' ir returned. + # If there is no valid escapemark, then an error is displayed ans null is returned. + # Return nulll if no such a label is found. + private fun get_escapemark(node: ANode, nlabel: nullable ALabel): nullable EscapeMark + do + if nlabel != null then + var name = nlabel.n_id.text + var res = search_label(name) + if res == null then + self.error(nlabel, "Syntax error: invalid label {name}.") + return null + end + return res + else + for scope in scopes do + var res = scope.escapemark + if res != null and res.for_loop then + return res + end + end + self.error(node, "Syntax Error: 'break' statment outside block.") + return null + end + end + + # Display an error + private fun error(node: ANode, message: String) + do + self.toolcontext.error(node.hot_location, message) + end +end + +private class Scope + var variables: HashMap[String, Variable] = new HashMap[String, Variable] + + var escapemark: nullable EscapeMark = null + + fun get_variable(name: String): nullable Variable + do + if self.variables.has_key(name) then + return self.variables[name] + else + return null + end + end +end + +redef class ANode + private fun accept_scope_visitor(v: ScopeVisitor) + do + visit_all(v) + end +end + +redef class APropdef + # Entry point of the scope analysis + fun do_scope(toolcontext: ToolContext) + do + var v = new ScopeVisitor(toolcontext) + v.enter_visit(self) + end +end + +redef class AParam + # The variable associated with the parameter + var variable: nullable Variable + redef fun accept_scope_visitor(v) + do + super + var nid = self.n_id + var variable = new Variable(nid.text) + v.register_variable(nid, variable) + self.variable = variable + end +end + +redef class AClosureDecl + # The variable associated with the closure declaration + var variable: nullable ClosureVariable + redef fun accept_scope_visitor(v) + do + var nid = self.n_id + var variable = new ClosureVariable(nid.text) + v.register_variable(nid, variable) + self.variable = variable + end +end + +redef class AVardeclExpr + # The variable associated with the variable declaration + var variable: nullable Variable + redef fun accept_scope_visitor(v) + do + super + var nid = self.n_id + var variable = new Variable(nid.text) + v.register_variable(nid, variable) + self.variable = variable + end +end + +redef class AContinueExpr + # The escape mark associated with the continue + var escapemark: nullable EscapeMark + redef fun accept_scope_visitor(v) + do + super + var escapemark = v.get_escapemark(self, self.n_label) + if escapemark == null then return # Skip error + if not escapemark.for_loop then + v.error(self, "Error: cannot 'continue', only 'break'.") + end + escapemark.continues.add(self) + self.escapemark = escapemark + end +end + +redef class ABreakExpr + # The escape mark associated with the break + var escapemark: nullable EscapeMark + redef fun accept_scope_visitor(v) + do + super + var escapemark = v.get_escapemark(self, self.n_label) + if escapemark == null then return # Skip error + escapemark.breaks.add(self) + self.escapemark = escapemark + end +end + + +redef class ADoExpr + # The escape mark associated with the 'do' block + var escapemark: nullable EscapeMark + redef fun accept_scope_visitor(v) + do + if n_label != null then + self.escapemark = v.make_escape_mark(n_label, false) + end + v.enter_visit_block(n_block, self.escapemark) + end +end + +redef class AIfExpr + redef fun accept_scope_visitor(v) + do + v.enter_visit(n_expr) + v.enter_visit_block(n_then, null) + v.enter_visit_block(n_else, null) + end +end + +redef class AWhileExpr + # The escape mark associated with the 'while' + var escapemark: nullable EscapeMark + redef fun accept_scope_visitor(v) + do + var escapemark = v.make_escape_mark(n_label, true) + self.escapemark = escapemark + v.enter_visit(n_expr) + v.enter_visit_block(n_block, escapemark) + end +end + +redef class ALoopExpr + # The escape mark associated with the 'loop' + var escapemark: nullable EscapeMark + redef fun accept_scope_visitor(v) + do + var escapemark = v.make_escape_mark(n_label, true) + self.escapemark = escapemark + v.enter_visit_block(n_block, escapemark) + end +end + +redef class AForExpr + # The automatic variables in order + var variables: nullable Array[Variable] + + # The escape mark associated with the 'for' + var escapemark: nullable EscapeMark + + redef fun accept_scope_visitor(v) + do + v.enter_visit(n_expr) + + # Protect automatic variables + v.scopes.unshift(new Scope) + + # Create the automatic variables + var variables = new Array[Variable] + self.variables = variables + for nid in n_ids do + var va = new Variable(nid.text) + v.register_variable(nid, va) + variables.add(va) + end + + var escapemark = v.make_escape_mark(n_label, true) + self.escapemark = escapemark + v.enter_visit_block(n_block, escapemark) + + v.scopes.shift + end +end + +redef class AVarFormExpr + # The associated variable + var variable: nullable Variable +end + +redef class ACallFormExpr + redef fun accept_scope_visitor(v) + do + if n_expr isa AImplicitSelfExpr then + var name = n_id.text + var variable = v.search_variable(name) + if variable != null then + var n: AExpr + if variable isa ClosureVariable then + n = new AClosureCallExpr.init_aclosurecallexpr(n_id, n_args, n_closure_defs) + n.variable = variable + else + if not n_args.n_exprs.is_empty or n_args isa AParExprs then + v.error(self, "Error: {name} is variable, not a function.") + return + end + n = variable_create(variable) + n.variable = variable + end + replace_with(n) + n.accept_scope_visitor(v) + return + end + end + + super + end + + # Create a variable acces corresponding to the call form + private fun variable_create(variable: Variable): AVarFormExpr is abstract +end + +redef class ACallExpr + redef fun variable_create(variable) + do + return new AVarExpr.init_avarexpr(n_id) + end +end + +redef class ACallAssignExpr + redef fun variable_create(variable) + do + return new AVarAssignExpr.init_avarassignexpr(n_id, n_assign, n_value) + end +end + +redef class ACallReassignExpr + redef fun variable_create(variable) + do + return new AVarReassignExpr.init_avarreassignexpr(n_id, n_assign_op, n_value) + end +end + +redef class AClosureCallExpr + # the associate closure variable + var variable: nullable ClosureVariable +end + +redef class AClosureDef + # The automatic variables in order + var variables: nullable Array[Variable] + + # The escape mark used with the closure + var escapemark: nullable EscapeMark + + redef fun accept_scope_visitor(v) + do + v.scopes.unshift(new Scope) + + var variables = new Array[Variable] + self.variables = variables + + for nid in self.n_ids do + var va = new Variable(nid.text) + v.register_variable(nid, va) + variables.add(va) + end + + var escapemark = v.make_escape_mark(n_label, true) + self.escapemark = escapemark + v.enter_visit_block(self.n_expr, escapemark) + + v.scopes.shift + end +end diff --git a/src/simple_misc_analysis.nit b/src/simple_misc_analysis.nit new file mode 100644 index 0000000..bc6c945 --- /dev/null +++ b/src/simple_misc_analysis.nit @@ -0,0 +1,176 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Simple vavious processing on a AST +# The analysis warns on : +# * superfluous parentheses +# * nested "once" expressions +# * use of "while true" instead of "loop" +package simple_misc_analysis + +import toolcontext +import parser + +redef class AModule + # Visit the module to detect easy warnings that does not need the metamodel or the importation + # Warnings are displayed on the toolcontext + fun do_simple_misc_analysis(toolcontext: ToolContext) + do + var v = new SimpleMiscVisitor(toolcontext) + v.enter_visit(self) + end +end + +private class SimpleMiscVisitor + super Visitor + redef fun visit(n) + do + if n != null then n.accept_simple_misc(self) + end + + # Number of nested once + var once_count: Int = 0 + + var toolcontext: ToolContext + + fun warning(node: ANode, msg: String) + do + toolcontext.warning(node.hot_location, msg) + end + + init(toolcontext: ToolContext) + do + self.toolcontext = toolcontext + end +end + + +############################################################################### + +redef class ANode + private fun accept_simple_misc(v: SimpleMiscVisitor) + do + visit_all(v) + after_simple_misc(v) + end + private fun after_simple_misc(v: SimpleMiscVisitor) do end +end + +redef class ASignature + redef fun after_simple_misc(v) + do + if self.n_opar != null and self.n_params.is_empty then + v.warning(self, "Warning: superfluous parentheses.") + end + end +end + +redef class AExpr + # Warn in case of superfluous parentheses + private fun warn_parentheses(v: SimpleMiscVisitor) do end +end + +redef class AParExpr + redef fun warn_parentheses(v) + do + v.warning(self, "Warning: superfluous parentheses.") + end +end + +redef class AParExprs + redef fun after_simple_misc(v) + do + if n_exprs.is_empty then + v.warning(self, "Warning: superfluous parentheses.") + end + end +end + +redef class AReturnExpr + redef fun after_simple_misc(v) + do + var e = n_expr + if e != null then + e.warn_parentheses(v) + end + end +end + +redef class AContinueExpr + redef fun after_simple_misc(v) + do + var e = n_expr + if e != null then + e.warn_parentheses(v) + end + end +end + +redef class ABreakExpr + redef fun after_simple_misc(v) + do + var e = n_expr + if e != null then + e.warn_parentheses(v) + end + end +end + +redef class AWhileExpr + redef fun after_simple_misc(v) + do + if n_expr isa ATrueExpr then + v.warning(self, "Warning: use 'loop' instead of 'while true do'.") + else + n_expr.warn_parentheses(v) + end + end +end + +redef class AForExpr + redef fun after_simple_misc(v) + do + n_expr.warn_parentheses(v) + end +end + +redef class AIfExpr + redef fun after_simple_misc(v) + do + n_expr.warn_parentheses(v) + end +end + +redef class AIfexprExpr + redef fun after_simple_misc(v) + do + n_expr.warn_parentheses(v) + end +end + +redef class AOnceExpr + redef fun accept_simple_misc(v) + do + if v.once_count > 0 then + v.warning(self, "Useless once in a once expression.") + end + v.once_count = v.once_count + 1 + + super + + v.once_count = v.once_count - 1 + end +end diff --git a/src/typing.nit b/src/typing.nit new file mode 100644 index 0000000..836a82b --- /dev/null +++ b/src/typing.nit @@ -0,0 +1,1448 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# Copyright 2012 Jean Privat +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +# Intraprocedural resolution of static types and OO-services +# By OO-services we mean message sending, attribute access, instantiation, etc. +module typing + +import flow +import modelbuilder + +private class TypeVisitor + var modelbuilder: ModelBuilder + var nclassdef: AClassdef + var mpropdef: MPropDef + + var selfvariable: Variable = new Variable("self") + + init(modelbuilder: ModelBuilder, nclassdef: AClassdef, mpropdef: MPropDef) + do + self.modelbuilder = modelbuilder + self.nclassdef = nclassdef + self.mpropdef = mpropdef + + var mclass = nclassdef.mclassdef.mclass + + var selfvariable = new Variable("self") + self.selfvariable = selfvariable + selfvariable.declared_type = mclass.mclass_type + end + + fun mmodule: MModule do return self.nclassdef.mclassdef.mmodule + + fun anchor: MClassType do return self.nclassdef.mclassdef.bound_mtype + + fun anchor_to(mtype: MType): MType + do + var mmodule = self.nclassdef.mclassdef.mmodule + var anchor = self.nclassdef.mclassdef.bound_mtype + return mtype.anchor_to(mmodule, anchor) + end + + fun is_subtype(sub, sup: MType): Bool + do + var mmodule = self.nclassdef.mclassdef.mmodule + var anchor = self.nclassdef.mclassdef.bound_mtype + return sub.is_subtype(mmodule, anchor, sup) + end + + fun resolve_for(mtype, subtype: MType, for_self: Bool): MType + do + var mmodule = self.nclassdef.mclassdef.mmodule + var anchor = self.nclassdef.mclassdef.bound_mtype + #print "resolve_for {mtype} sub={subtype} forself={for_self} mmodule={mmodule} anchor={anchor}" + var res = mtype.resolve_for(subtype, anchor, mmodule, not for_self) + return res + end + + fun resolve_signature_for(msignature: MSignature, recv: MType, for_self: Bool): MSignature + do + return self.resolve_for(msignature, recv, for_self).as(MSignature) + end + + fun check_subtype(node: ANode, sub, sup: MType): Bool + do + if self.is_subtype(sub, sup) then return true + if self.is_subtype(sub, self.anchor_to(sup)) then + # FIXME workarround to the current unsafe typing policy. To remove once fixed virtual types exists. + #node.debug("Unsafe typing: expected {sup}, got {sub}") + return true + end + self.modelbuilder.error(node, "Type error: expected {sup}, got {sub}") + return false + end + + # Visit an expression and do not care about the return value + fun visit_stmt(nexpr: nullable AExpr) + do + if nexpr == null then return + nexpr.accept_typing(self) + end + + # Visit an expression and expects that it is not a statement + # Return the type of the expression + # Display an error and return null if: + # * the type cannot be determined or + # * `nexpr' is a statement + fun visit_expr(nexpr: AExpr): nullable MType + do + nexpr.accept_typing(self) + var mtype = nexpr.mtype + if mtype != null then return mtype + if not nexpr.is_typed then + if not self.modelbuilder.toolcontext.error_count > 0 then # check that there is really an error + if self.modelbuilder.toolcontext.verbose_level > 1 then + nexpr.debug("No return type but no error.") + end + end + return null # forward error + end + self.error(nexpr, "Type error: expected expression.") + return null + end + + # Visit an expression and expect its static type is a least a `sup' + # Return the type of the expression + # * the type cannot be determined or + # * `nexpr' is a statement + # * `nexpt' is not a `sup' + fun visit_expr_subtype(nexpr: AExpr, sup: nullable MType): nullable MType + do + var sub = visit_expr(nexpr) + if sub == null then return null # Forward error + + if sup == null then return null # Forward error + + if not check_subtype(nexpr, sub, sup) then + return null + end + return sub + end + + # Visit an expression and expect its static type is a bool + # Return the type of the expression + # * the type cannot be determined or + # * `nexpr' is a statement + # * `nexpt' is not a `sup' + fun visit_expr_bool(nexpr: AExpr): nullable MType + do + return self.visit_expr_subtype(nexpr, self.type_bool(nexpr)) + end + + + private fun visit_expr_cast(node: ANode, nexpr: AExpr, ntype: AType): nullable MType + do + var sub = visit_expr(nexpr) + if sub == null then return null # Forward error + + var sup = self.resolve_mtype(ntype) + if sup == null then return null # Forward error + + var mmodule = self.nclassdef.mclassdef.mmodule + var anchor = self.nclassdef.mclassdef.bound_mtype + if sup == sub then + self.modelbuilder.warning(node, "Warning: Expression is already a {sup}.") + else if self.is_subtype(sub, sup) and not sup.need_anchor then + self.modelbuilder.warning(node, "Warning: Expression is already a {sup} since it is a {sub}.") + end + return sup + end + + fun try_get_mproperty_by_name2(anode: ANode, mtype: MType, name: String): nullable MProperty + do + return self.modelbuilder.try_get_mproperty_by_name2(anode, self.nclassdef.mclassdef.mmodule, mtype, name) + end + + fun resolve_mtype(node: AType): nullable MType + do + return self.modelbuilder.resolve_mtype(self.nclassdef, node) + end + + fun get_mclass(node: ANode, name: String): nullable MClass + do + var mmodule = self.nclassdef.mclassdef.mmodule + var mclass = modelbuilder.try_get_mclass_by_name(node, mmodule, name) + if mclass == null then + self.modelbuilder.error(node, "Type Error: missing primitive class `{name}'.") + end + return mclass + end + + fun type_bool(node: ANode): nullable MType + do + var mclass = self.get_mclass(node, "Bool") + if mclass == null then return null + return mclass.mclass_type + end + + fun get_method(node: ANode, recvtype: MType, name: String, recv_is_self: Bool): nullable MMethodDef + do + var unsafe_type = self.anchor_to(recvtype) + + #debug("recv: {recvtype} (aka {unsafe_type})") + + var mproperty = self.try_get_mproperty_by_name2(node, unsafe_type, name) + if mproperty == null then + #self.modelbuilder.error(node, "Type error: property {name} not found in {unsafe_type} (ie {recvtype})") + if recv_is_self then + self.modelbuilder.error(node, "Error: Method or variable '{name}' unknown in {recvtype}.") + else + self.modelbuilder.error(node, "Error: Method '{name}' doesn't exists in {recvtype}.") + end + return null + end + + var propdefs = mproperty.lookup_definitions(self.mmodule, unsafe_type) + if propdefs.length == 0 then + self.modelbuilder.error(node, "Type error: no definition found for property {name} in {unsafe_type}") + return null + else if propdefs.length > 1 then + self.modelbuilder.error(node, "Error: confliting property definitions for property {name} in {unsafe_type}: {propdefs.join(" ")}") + return null + end + + var propdef = propdefs.first + assert propdef isa MMethodDef + return propdef + end + + # Visit the expressions of args and cheik their conformity with the corresponding typi in signature + # The point of this method is to handle varargs correctly + # Note: The signature must be correctly adapted + fun check_signature(node: ANode, args: Array[AExpr], name: String, msignature: MSignature): Bool + do + var vararg_rank = msignature.vararg_rank + if vararg_rank >= 0 then + if args.length < msignature.arity then + #self.modelbuilder.error(node, "Error: Incorrect number of parameters. Got {args.length}, expected at least {msignature.arity}. Signature is {msignature}") + self.modelbuilder.error(node, "Error: arity mismatch; prototype is '{name}{msignature}'") + return false + end + else if args.length != msignature.arity then + self.modelbuilder.error(node, "Error: Incorrect number of parameters. Got {args.length}, expected {msignature.arity}. Signature is {msignature}") + return false + end + + #debug("CALL {unsafe_type}.{msignature}") + + var vararg_decl = args.length - msignature.arity + for i in [0..msignature.arity[ do + var j = i + if i == vararg_rank then continue # skip the vararg + if i > vararg_rank then + j = i + vararg_decl + end + var paramtype = msignature.parameter_mtypes[i] + self.visit_expr_subtype(args[j], paramtype) + end + if vararg_rank >= 0 then + var varargs = new Array[AExpr] + var paramtype = msignature.parameter_mtypes[vararg_rank] + for j in [vararg_rank..vararg_rank+vararg_decl] do + varargs.add(args[j]) + self.visit_expr_subtype(args[j], paramtype) + end + end + return true + end + + fun error(node: ANode, message: String) + do + self.modelbuilder.toolcontext.error(node.hot_location, message) + end + + fun get_variable(node: AExpr, variable: Variable): nullable MType + do + var flow = node.after_flow_context + if flow == null then + self.error(node, "No context!") + return null + end + + if flow.vars.has_key(variable) then + return flow.vars[variable] + else + #node.debug("*** START Collected for {variable}") + var mtypes = flow.collect_types(variable) + #node.debug("**** END Collected for {variable}") + if mtypes == null or mtypes.length == 0 then + return variable.declared_type + else if mtypes.length == 1 then + return mtypes.first + else + var res = merge_types(node,mtypes) + if res == null then res = variable.declared_type + return res + end + end + end + + fun set_variable(node: AExpr, variable: Variable, mtype: nullable MType) + do + var flow = node.after_flow_context + assert flow != null + + flow.set_var(variable, mtype) + end + + fun merge_types(node: ANode, col: Array[nullable MType]): nullable MType + do + if col.length == 1 then return col.first + var res = new Array[nullable MType] + for t1 in col do + if t1 == null then continue # return null + var found = true + for t2 in col do + if t2 == null then continue # return null + if t2 isa MNullableType or t2 isa MNullType then + t1 = t1.as_nullable + end + if not is_subtype(t2, t1) then found = false + end + if found then + #print "merge {col.join(" ")} -> {t1}" + return t1 + end + end + #self.modelbuilder.warning(node, "Type Error: {col.length} conflicting types: <{col.join(", ")}>") + return null + end +end + +redef class Variable + # The declared type of the variable + var declared_type: nullable MType +end + +redef class FlowContext + # Store changes of types because of type evolution + private var vars: HashMap[Variable, nullable MType] = new HashMap[Variable, nullable MType] + private var cache: HashMap[Variable, nullable Array[nullable MType]] = new HashMap[Variable, nullable Array[nullable MType]] + + # Adapt the variable to a static type + # Warning1: do not modify vars directly. + # Warning2: sub-flow may have cached a unadapted variabial + private fun set_var(variable: Variable, mtype: nullable MType) + do + self.vars[variable] = mtype + self.cache.keys.remove(variable) + end + + private fun collect_types(variable: Variable): nullable Array[nullable MType] + do + if cache.has_key(variable) then + return cache[variable] + end + var res: nullable Array[nullable MType] = null + if vars.has_key(variable) then + var mtype = vars[variable] + res = [mtype] + else if self.previous.is_empty then + # Root flow + res = [variable.declared_type] + else + for flow in self.previous do + if flow.is_unreachable then continue + var r2 = flow.collect_types(variable) + if r2 == null then continue + if res == null then + res = r2.to_a + else + for t in r2 do + if not res.has(t) then res.add(t) + end + end + end + end + cache[variable] = res + return res + end +end + +redef class APropdef + # The entry point of the whole typing analysis + fun do_typing(modelbuilder: ModelBuilder) + do + end +end + +redef class AConcreteMethPropdef + redef fun do_typing(modelbuilder: ModelBuilder) + do + var nclassdef = self.parent.as(AClassdef) + var mpropdef = self.mpropdef.as(not null) + var v = new TypeVisitor(modelbuilder, nclassdef, mpropdef) + + var nblock = self.n_block + if nblock == null then return + + var mmethoddef = self.mpropdef.as(not null) + for i in [0..mmethoddef.msignature.arity[ do + var mtype = mmethoddef.msignature.parameter_mtypes[i] + if mmethoddef.msignature.vararg_rank == i then + var arrayclass = v.get_mclass(self.n_signature.n_params[i], "Array") + if arrayclass == null then return # Skip error + mtype = arrayclass.get_mtype([mtype]) + end + var variable = self.n_signature.n_params[i].variable + assert variable != null + variable.declared_type = mtype + end + v.visit_stmt(nblock) + + if not nblock.after_flow_context.is_unreachable and mmethoddef.msignature.return_mtype != null then + # We reach the end of the function without having a return, it is bad + v.error(self, "Control error: Reached end of function (a 'return' with a value was expected).") + end + end +end + +redef class AAttrPropdef + redef fun do_typing(modelbuilder: ModelBuilder) + do + var nclassdef = self.parent.as(AClassdef) + var v = new TypeVisitor(modelbuilder, nclassdef, self.mpropdef.as(not null)) + + var nexpr = self.n_expr + if nexpr != null then + var mtype = self.mpropdef.static_mtype + v.visit_expr_subtype(nexpr, mtype) + end + end +end + +### + +redef class AExpr + # The static type of the expression. + # null if self is a statement of in case of error + var mtype: nullable MType = null + + # Is the statement correctly typed. + # Used to distinguish errors and statements when `mtype' == null + var is_typed: Bool = false + + # Return the variable read (if any) + # Used to perform adaptive typing + fun its_variable: nullable Variable do return null + + private fun accept_typing(v: TypeVisitor) + do + v.error(self, "no implemented accept_typing for {self.class_name}") + end +end + +redef class ABlockExpr + redef fun accept_typing(v) + do + for e in self.n_expr do v.visit_stmt(e) + self.is_typed = true + end +end + +redef class AVardeclExpr + redef fun accept_typing(v) + do + var variable = self.variable + if variable == null then return # Skip error + + var ntype = self.n_type + var mtype: nullable MType + if ntype == null then + mtype = null + else + mtype = v.resolve_mtype(ntype) + if mtype == null then return # Skip error + end + + var nexpr = self.n_expr + if nexpr != null then + if mtype != null then + v.visit_expr_subtype(nexpr, mtype) + else + mtype = v.visit_expr(nexpr) + if mtype == null then return # Skip error + end + end + + if mtype == null then + mtype = v.get_mclass(self, "Object").mclass_type + end + + variable.declared_type = mtype + v.set_variable(self, variable, mtype) + + #debug("var {variable}: {mtype}") + + self.is_typed = true + end +end + +redef class AVarExpr + redef fun its_variable do return self.variable + redef fun accept_typing(v) + do + var variable = self.variable + if variable == null then return # Skip error + + var mtype = v.get_variable(self, variable) + if mtype != null then + #debug("{variable} is {mtype}") + else + #debug("{variable} is untyped") + end + + self.mtype = mtype + end +end + +redef class AVarAssignExpr + redef fun accept_typing(v) + do + var variable = self.variable + assert variable != null + + var mtype = v.visit_expr_subtype(n_value, variable.declared_type) + + v.set_variable(self, variable, mtype) + + self.is_typed = true + end +end + +redef class AReassignFormExpr + # The method designed by the reassign operator. + var reassign_property: nullable MMethodDef = null + + var read_type: nullable MType = null + + # Determine the `reassign_property' + # `readtype' is the type of the reading of the left value. + # `writetype' is the type of the writing of the left value. + # (Because of ACallReassignExpr, both can be different. + # Return the static type of the value to store. + private fun resolve_reassignment(v: TypeVisitor, readtype, writetype: MType): nullable MType + do + var reassign_name: String + if self.n_assign_op isa APlusAssignOp then + reassign_name = "+" + else if self.n_assign_op isa AMinusAssignOp then + reassign_name = "-" + else + abort + end + + self.read_type = readtype + + if readtype isa MNullType then + v.error(self, "Error: Method '{reassign_name}' call on 'null'.") + return null + end + + var mpropdef = v.get_method(self, readtype, reassign_name, false) + if mpropdef == null then return null # Skip error + + self.reassign_property = mpropdef + + var msignature = mpropdef.msignature + assert msignature!= null + msignature = v.resolve_signature_for(msignature, readtype, false) + + var rettype = msignature.return_mtype + assert msignature.arity == 1 and rettype != null + + var value_type = v.visit_expr_subtype(self.n_value, msignature.parameter_mtypes.first) + if value_type == null then return null # Skip error + + v.check_subtype(self, rettype, writetype) + return rettype + end +end + +redef class AVarReassignExpr + redef fun accept_typing(v) + do + var variable = self.variable + assert variable != null + + var readtype = v.get_variable(self, variable) + if readtype == null then return + + var writetype = variable.declared_type + if writetype == null then return + + var rettype = self.resolve_reassignment(v, readtype, writetype) + + v.set_variable(self, variable, rettype) + + self.is_typed = true + end +end + + +redef class AContinueExpr + redef fun accept_typing(v) + do + var nexpr = self.n_expr + if nexpr != null then + var mtype = v.visit_expr(nexpr) + end + self.is_typed = true + end +end + +redef class ABreakExpr + redef fun accept_typing(v) + do + var nexpr = self.n_expr + if nexpr != null then + var mtype = v.visit_expr(nexpr) + end + self.is_typed = true + end +end + +redef class AReturnExpr + redef fun accept_typing(v) + do + var nexpr = self.n_expr + var ret_type = v.mpropdef.as(MMethodDef).msignature.return_mtype + if nexpr != null then + if ret_type != null then + var mtype = v.visit_expr_subtype(nexpr, ret_type) + else + var mtype = v.visit_expr(nexpr) + v.error(self, "Error: Return with value in a procedure.") + end + else if ret_type != null then + v.error(self, "Error: Return without value in a function.") + end + self.is_typed = true + end +end + +redef class AAbortExpr + redef fun accept_typing(v) + do + self.is_typed = true + end +end + +redef class AIfExpr + redef fun accept_typing(v) + do + v.visit_expr_bool(n_expr) + + v.visit_stmt(n_then) + v.visit_stmt(n_else) + self.is_typed = true + end +end + +redef class AIfexprExpr + redef fun accept_typing(v) + do + v.visit_expr_bool(n_expr) + + var t1 = v.visit_expr(n_then) + var t2 = v.visit_expr(n_else) + + if t1 == null or t2 == null then + return # Skip error + end + + var t = v.merge_types(self, [t1, t2]) + if t == null then + v.error(self, "Type Error: ambiguous type {t1} vs {t2}") + end + self.mtype = t + end +end + +redef class ADoExpr + redef fun accept_typing(v) + do + v.visit_stmt(n_block) + self.is_typed = true + end +end + +redef class AWhileExpr + redef fun accept_typing(v) + do + v.visit_expr_bool(n_expr) + + v.visit_stmt(n_block) + self.is_typed = true + end +end + +redef class ALoopExpr + redef fun accept_typing(v) + do + v.visit_stmt(n_block) + self.is_typed = true + end +end + +redef class AForExpr + redef fun accept_typing(v) + do + var mtype = v.visit_expr(n_expr) + if mtype == null then return + + var colcla = v.get_mclass(self, "Collection") + if colcla == null then return + var objcla = v.get_mclass(self, "Object") + if objcla == null then return + if v.is_subtype(mtype, colcla.get_mtype([objcla.mclass_type.as_nullable])) then + var coltype = mtype.supertype_to(v.mmodule, v.anchor, colcla) + assert coltype isa MGenericType + var variables = self.variables + if variables.length != 1 then + v.error(self, "Type Error: Expected one variable") + else + variables.first.declared_type = coltype.arguments.first + end + else + v.modelbuilder.error(self, "TODO: Do 'for' on {mtype}") + end + + v.visit_stmt(n_block) + self.is_typed = true + end +end + +redef class AAssertExpr + redef fun accept_typing(v) + do + v.visit_expr_bool(n_expr) + + v.visit_stmt(n_else) + self.is_typed = true + end +end + +redef class AOrExpr + redef fun accept_typing(v) + do + v.visit_expr_bool(n_expr) + v.visit_expr_bool(n_expr2) + self.mtype = v.type_bool(self) + end +end + +redef class AAndExpr + redef fun accept_typing(v) + do + v.visit_expr_bool(n_expr) + v.visit_expr_bool(n_expr2) + self.mtype = v.type_bool(self) + end +end + + +redef class ANotExpr + redef fun accept_typing(v) + do + v.visit_expr_bool(n_expr) + self.mtype = v.type_bool(self) + end +end + +redef class AOrElseExpr + redef fun accept_typing(v) + do + var t1 = v.visit_expr(n_expr) + var t2 = v.visit_expr(n_expr2) + + if t1 == null or t2 == null then + return # Skip error + end + + if t1 isa MNullableType then + t1 = t1.mtype + end + + var t = v.merge_types(self, [t1, t2]) + if t == null then + v.error(self, "Type Error: ambiguous type {t1} vs {t2}") + end + self.mtype = t + end +end + +redef class AEeExpr + redef fun accept_typing(v) + do + v.visit_expr(n_expr) + v.visit_expr(n_expr2) + self.mtype = v.type_bool(self) + end +end + +redef class ATrueExpr + redef fun accept_typing(v) + do + self.mtype = v.type_bool(self) + end +end + +redef class AFalseExpr + redef fun accept_typing(v) + do + self.mtype = v.type_bool(self) + end +end + +redef class AIntExpr + redef fun accept_typing(v) + do + var mclass = v.get_mclass(self, "Int") + if mclass == null then return # Forward error + self.mtype = mclass.mclass_type + end +end + +redef class AFloatExpr + redef fun accept_typing(v) + do + var mclass = v.get_mclass(self, "Float") + if mclass == null then return # Forward error + self.mtype = mclass.mclass_type + end +end + +redef class ACharExpr + redef fun accept_typing(v) + do + var mclass = v.get_mclass(self, "Char") + if mclass == null then return # Forward error + self.mtype = mclass.mclass_type + end +end + +redef class AStringFormExpr + redef fun accept_typing(v) + do + var mclass = v.get_mclass(self, "String") + if mclass == null then return # Forward error + self.mtype = mclass.mclass_type + end +end + +redef class ASuperstringExpr + redef fun accept_typing(v) + do + var mclass = v.get_mclass(self, "String") + if mclass == null then return # Forward error + self.mtype = mclass.mclass_type + for nexpr in self.n_exprs do + var t = v.visit_expr(nexpr) + end + end +end + +redef class AArrayExpr + redef fun accept_typing(v) + do + var mtypes = new Array[nullable MType] + for e in self.n_exprs.n_exprs do + var t = v.visit_expr(e) + if t == null then + return # Skip error + end + mtypes.add(t) + end + var mtype = v.merge_types(self, mtypes) + if mtype == null then + v.error(self, "Type Error: ambiguous array type {mtypes.join(" ")}") + return + end + var mclass = v.get_mclass(self, "Array") + if mclass == null then return # Forward error + self.mtype = mclass.get_mtype([mtype]) + end +end + +redef class ARangeExpr + redef fun accept_typing(v) + do + var t1 = v.visit_expr(self.n_expr) + var t2 = v.visit_expr(self.n_expr2) + if t1 == null or t2 == null then return + var mclass = v.get_mclass(self, "Range") + if mclass == null then return # Forward error + if v.is_subtype(t1, t2) then + self.mtype = mclass.get_mtype([t2]) + else if v.is_subtype(t2, t1) then + self.mtype = mclass.get_mtype([t1]) + else + v.error(self, "Type Error: Cannot create range: {t1} vs {t2}") + end + end +end + +redef class ANullExpr + redef fun accept_typing(v) + do + self.mtype = v.mmodule.model.null_type + end +end + +redef class AIsaExpr + # The static type to cast to. + # (different from the static type of the expression that is Bool). + var cast_type: nullable MType + redef fun accept_typing(v) + do + var mtype = v.visit_expr_cast(self, self.n_expr, self.n_type) + self.cast_type = mtype + + var variable = self.n_expr.its_variable + if variable != null then + var orig = self.n_expr.mtype + var from = if orig != null then orig.to_s else "invalid" + var to = if mtype != null then mtype.to_s else "invalid" + #debug("adapt {variable}: {from} -> {to}") + self.after_flow_context.when_true.set_var(variable, mtype) + end + + self.mtype = v.type_bool(self) + end +end + +redef class AAsCastExpr + redef fun accept_typing(v) + do + self.mtype = v.visit_expr_cast(self, self.n_expr, self.n_type) + end +end + +redef class AAsNotnullExpr + redef fun accept_typing(v) + do + var mtype = v.visit_expr(self.n_expr) + if mtype isa MNullType then + v.error(self, "Type error: as(not null) on null") + return + end + if mtype isa MNullableType then + self.mtype = mtype.mtype + return + end + # TODO: warn on useless as not null + self.mtype = mtype + end +end + +redef class AProxyExpr + redef fun accept_typing(v) + do + self.mtype = v.visit_expr(self.n_expr) + end +end + +redef class ASelfExpr + redef var its_variable: nullable Variable + redef fun accept_typing(v) + do + var variable = v.selfvariable + self.its_variable = variable + self.mtype = v.get_variable(self, variable) + end +end + +## MESSAGE SENDING AND PROPERTY + +redef class ASendExpr + # The property invoked by the send. + var mproperty: nullable MMethod + + redef fun accept_typing(v) + do + var recvtype = v.visit_expr(self.n_expr) + var name = self.property_name + + if recvtype == null then return # Forward error + if recvtype isa MNullType then + v.error(self, "Error: Method '{name}' call on 'null'.") + return + end + + var propdef = v.get_method(self, recvtype, name, self.n_expr isa ASelfExpr) + if propdef == null then return + var mproperty = propdef.mproperty + self.mproperty = mproperty + var msignature = propdef.msignature + if msignature == null then abort # Forward error + + var for_self = self.n_expr isa ASelfExpr + msignature = v.resolve_signature_for(msignature, recvtype, for_self) + + var args = compute_raw_arguments + + v.check_signature(self, args, name, msignature) + + if mproperty.is_init then + var vmpropdef = v.mpropdef + if not (vmpropdef isa MMethodDef and vmpropdef.mproperty.is_init) then + v.error(self, "Can call a init only in another init") + end + end + + var ret = msignature.return_mtype + if ret != null then + self.mtype = ret + else + self.is_typed = true + end + end + + # The name of the property + # Each subclass simply provide the correct name. + private fun property_name: String is abstract + + # An array of all arguments (excluding self) + fun compute_raw_arguments: Array[AExpr] is abstract +end + +redef class ABinopExpr + redef fun compute_raw_arguments do return [n_expr2] +end +redef class AEqExpr + redef fun property_name do return "==" + redef fun accept_typing(v) + do + super + + var variable = self.n_expr.its_variable + if variable == null then return + var mtype = self.n_expr2.mtype + if not mtype isa MNullType then return + var vartype = v.get_variable(self, variable) + if not vartype isa MNullableType then return + self.after_flow_context.when_true.set_var(variable, mtype) + self.after_flow_context.when_false.set_var(variable, vartype.mtype) + #debug("adapt {variable}:{vartype} ; true->{mtype} false->{vartype.mtype}") + end +end +redef class ANeExpr + redef fun property_name do return "!=" + redef fun accept_typing(v) + do + super + + var variable = self.n_expr.its_variable + if variable == null then return + var mtype = self.n_expr2.mtype + if not mtype isa MNullType then return + var vartype = v.get_variable(self, variable) + if not vartype isa MNullableType then return + self.after_flow_context.when_false.set_var(variable, mtype) + self.after_flow_context.when_true.set_var(variable, vartype.mtype) + #debug("adapt {variable}:{vartype} ; true->{vartype.mtype} false->{mtype}") + end +end +redef class ALtExpr + redef fun property_name do return "<" +end +redef class ALeExpr + redef fun property_name do return "<=" +end +redef class ALlExpr + redef fun property_name do return "<<" +end +redef class AGtExpr + redef fun property_name do return ">" +end +redef class AGeExpr + redef fun property_name do return ">=" +end +redef class AGgExpr + redef fun property_name do return ">>" +end +redef class APlusExpr + redef fun property_name do return "+" +end +redef class AMinusExpr + redef fun property_name do return "-" +end +redef class AStarshipExpr + redef fun property_name do return "<=>" +end +redef class AStarExpr + redef fun property_name do return "*" +end +redef class ASlashExpr + redef fun property_name do return "/" +end +redef class APercentExpr + redef fun property_name do return "%" +end + +redef class AUminusExpr + redef fun property_name do return "unary -" + redef fun compute_raw_arguments do return new Array[AExpr] +end + + +redef class ACallExpr + redef fun property_name do return n_id.text + redef fun compute_raw_arguments do return n_args.to_a +end + +redef class ACallAssignExpr + redef fun property_name do return n_id.text + "=" + redef fun compute_raw_arguments + do + var res = n_args.to_a + res.add(n_value) + return res + end +end + +redef class ABraExpr + redef fun property_name do return "[]" + redef fun compute_raw_arguments do return n_args.to_a +end + +redef class ABraAssignExpr + redef fun property_name do return "[]=" + redef fun compute_raw_arguments + do + var res = n_args.to_a + res.add(n_value) + return res + end +end + +redef class ASendReassignFormExpr + # The property invoked for the writing + var write_mproperty: nullable MMethod = null + + redef fun accept_typing(v) + do + var recvtype = v.visit_expr(self.n_expr) + var name = self.property_name + + if recvtype == null then return # Forward error + if recvtype isa MNullType then + v.error(self, "Error: Method '{name}' call on 'null'.") + return + end + + var propdef = v.get_method(self, recvtype, name, self.n_expr isa ASelfExpr) + if propdef == null then return + var mproperty = propdef.mproperty + self.mproperty = mproperty + var msignature = propdef.msignature + if msignature == null then abort # Forward error + var for_self = self.n_expr isa ASelfExpr + msignature = v.resolve_signature_for(msignature, recvtype, for_self) + + var args = compute_raw_arguments + + v.check_signature(self, args, name, msignature) + + var readtype = msignature.return_mtype + if readtype == null then + v.error(self, "Error: {name} is not a function") + return + end + + var wpropdef = v.get_method(self, recvtype, name + "=", self.n_expr isa ASelfExpr) + if wpropdef == null then return + var wmproperty = wpropdef.mproperty + self.write_mproperty = wmproperty + var wmsignature = wpropdef.msignature + if wmsignature == null then abort # Forward error + wmsignature = v.resolve_signature_for(wmsignature, recvtype, for_self) + + var wtype = self.resolve_reassignment(v, readtype, wmsignature.parameter_mtypes.last) + if wtype == null then return + + args.add(self.n_value) + v.check_signature(self, args, name + "=", wmsignature) + + self.is_typed = true + end +end + +redef class ACallReassignExpr + redef fun property_name do return n_id.text + redef fun compute_raw_arguments do return n_args.to_a +end + +redef class ABraReassignExpr + redef fun property_name do return "[]" + redef fun compute_raw_arguments do return n_args.to_a +end + +redef class AInitExpr + redef fun property_name do return "init" + redef fun compute_raw_arguments do return n_args.to_a +end + +redef class AExprs + fun to_a: Array[AExpr] do return self.n_exprs.to_a +end + +### + +redef class ASuperExpr + # The method to call if the super is in fact a 'super init call' + # Note: if the super is a normal call-next-method, then this attribute is null + var mproperty: nullable MMethod + + redef fun accept_typing(v) + do + var recvtype = v.nclassdef.mclassdef.bound_mtype + var mproperty = v.mpropdef.mproperty + if not mproperty isa MMethod then + v.error(self, "Error: super only usable in a method") + return + end + var superprops = mproperty.lookup_super_definitions(v.mmodule, recvtype) + if superprops.length == 0 then + if mproperty.is_init and v.mpropdef.is_intro then + process_superinit(v) + return + end + v.error(self, "Error: No super method to call for {mproperty}.") + return + else if superprops.length > 1 then + v.modelbuilder.warning(self, "Error: Conflicting super method to call for {mproperty}: {superprops.join(", ")}.") + return + end + var superprop = superprops.first + assert superprop isa MMethodDef + + var msignature = superprop.msignature.as(not null) + msignature = v.resolve_signature_for(msignature, recvtype, true) + var args = self.n_args.to_a + if args.length > 0 then + v.check_signature(self, args, mproperty.name, msignature) + end + self.mtype = msignature.return_mtype + end + + private fun process_superinit(v: TypeVisitor) + do + var recvtype = v.nclassdef.mclassdef.bound_mtype + var mproperty = v.mpropdef.mproperty + var superprop: nullable MMethodDef = null + for msupertype in v.nclassdef.mclassdef.supertypes do + msupertype = msupertype.anchor_to(v.mmodule, recvtype) + var errcount = v.modelbuilder.toolcontext.error_count + var candidate = v.try_get_mproperty_by_name2(self, msupertype, mproperty.name).as(nullable MMethod) + if candidate == null then + if v.modelbuilder.toolcontext.error_count > errcount then return # Forard error + continue # Try next super-class + end + if superprop != null and superprop.mproperty != candidate then + v.error(self, "Error: conflicting super constructor to call for {mproperty}: {candidate.full_name}, {superprop.mproperty.full_name}") + return + end + var candidatedefs = candidate.lookup_definitions(v.mmodule, recvtype) + if superprop != null then + if superprop == candidatedefs.first then continue + candidatedefs.add(superprop) + end + if candidatedefs.length > 1 then + v.error(self, "Error: confliting property definitions for property {mproperty} in {recvtype}: {candidatedefs.join(", ")}") + return + end + superprop = candidatedefs.first + end + if superprop == null then + v.error(self, "Error: No super method to call for {mproperty}.") + return + end + self.mproperty = superprop.mproperty + + var args = self.n_args.to_a + var msignature = superprop.msignature.as(not null) + msignature = v.resolve_signature_for(msignature, recvtype, true) + if args.length > 0 then + v.check_signature(self, args, mproperty.name, msignature) + else + # TODO: Check signature + end + + self.is_typed = true + end +end + +#### + +redef class ANewExpr + # The constructor invoked by the new. + var mproperty: nullable MMethod + + redef fun accept_typing(v) + do + var recvtype = v.resolve_mtype(self.n_type) + if recvtype == null then return + self.mtype = recvtype + + if not recvtype isa MClassType then + if recvtype isa MNullableType then + v.error(self, "Type error: cannot instantiate the nullable type {recvtype}.") + return + else + v.error(self, "Type error: cannot instantiate the formal type {recvtype}.") + return + end + end + + var name: String + var nid = self.n_id + if nid != null then + name = nid.text + else + name = "init" + end + var propdef = v.get_method(self, recvtype, name, false) + if propdef == null then return + + self.mproperty = propdef.mproperty + + if not propdef.mproperty.is_init_for(recvtype.mclass) then + v.error(self, "Error: {name} is not a constructor.") + return + end + + var msignature = propdef.msignature.as(not null) + msignature = v.resolve_signature_for(msignature, recvtype, false) + + var args = n_args.to_a + v.check_signature(self, args, name, msignature) + end +end + +#### + +redef class AAttrFormExpr + # The attribute acceded. + var mproperty: nullable MAttribute + + # The static type of the attribute. + var attr_type: nullable MType + + # Resolve the attribute acceded. + private fun resolve_property(v: TypeVisitor) + do + var recvtype = v.visit_expr(self.n_expr) + if recvtype == null then return # Skip error + var name = self.n_id.text + if recvtype isa MNullType then + v.error(self, "Error: Attribute '{name}' access on 'null'.") + return + end + + var unsafe_type = v.anchor_to(recvtype) + var mproperty = v.try_get_mproperty_by_name2(self, unsafe_type, name) + if mproperty == null then + v.modelbuilder.error(self, "Error: Attribute {name} doesn't exists in {recvtype}.") + return + end + assert mproperty isa MAttribute + self.mproperty = mproperty + + var mpropdefs = mproperty.lookup_definitions(v.mmodule, unsafe_type) + assert mpropdefs.length == 1 + var mpropdef = mpropdefs.first + var attr_type = mpropdef.static_mtype.as(not null) + attr_type = v.resolve_for(attr_type, recvtype, self.n_expr isa ASelfExpr) + self.attr_type = attr_type + end +end + +redef class AAttrExpr + redef fun accept_typing(v) + do + self.resolve_property(v) + self.mtype = self.attr_type + end +end + + +redef class AAttrAssignExpr + redef fun accept_typing(v) + do + self.resolve_property(v) + var mtype = self.attr_type + + v.visit_expr_subtype(self.n_value, mtype) + self.is_typed = true + end +end + +redef class AAttrReassignExpr + redef fun accept_typing(v) + do + self.resolve_property(v) + var mtype = self.attr_type + if mtype == null then return # Skip error + + self.resolve_reassignment(v, mtype, mtype) + + self.is_typed = true + end +end + +redef class AIssetAttrExpr + redef fun accept_typing(v) + do + self.resolve_property(v) + var mtype = self.attr_type + if mtype == null then return # Skip error + + var recvtype = self.n_expr.mtype.as(not null) + var bound = v.resolve_for(mtype, recvtype, false) + if bound isa MNullableType then + v.error(self, "Error: isset on a nullable attribute.") + end + self.mtype = v.type_bool(self) + end +end + +### + +redef class AClosureCallExpr + redef fun accept_typing(v) + do + #TODO + end +end + +### + +redef class ADebugTypeExpr + redef fun accept_typing(v) + do + var expr = v.visit_expr(self.n_expr) + if expr == null then return + var unsafe = v.anchor_to(expr) + var ntype = self.n_type + var mtype = v.resolve_mtype(ntype) + if mtype != null and mtype != expr then + var umtype = v.anchor_to(mtype) + v.modelbuilder.warning(self, "Found type {expr} (-> {unsafe}), expected {mtype} (-> {umtype})") + end + end +end -- 1.7.9.5