Menu
▾
▴
[Rubyeclipse-commit] SF.net SVN: rubyeclipse: [1576] branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti
|
From: <jas...@us...> - 2006-08-21 08:31:00
|
Revision: 1576 Author: jasonpmorrison Date: 2006-08-21 01:30:19 -0700 (Mon, 21 Aug 2006) ViewCVS: http://svn.sourceforge.net/rubyeclipse/?rev=1576&view=rev Log Message: ----------- * First rough cut of DataFlowTypeInferrer! Modified Paths: -------------- branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/util/ClosestSpanningNodeLocator.java branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/util/MethodDefinitionLocator.java Added Paths: ----------- branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/DataFlowTypeInferrer.java branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/TypeInferenceHelper.java branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/util/MethodInvocationLocator.java Added: branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/DataFlowTypeInferrer.java =================================================================== --- branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/DataFlowTypeInferrer.java (rev 0) +++ branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/DataFlowTypeInferrer.java 2006-08-21 08:30:19 UTC (rev 1576) @@ -0,0 +1,578 @@ +package org.rubypeople.rdt.internal.ti; + +import java.util.ArrayList; +import java.util.LinkedList; +import java.util.List; + +import org.jruby.ast.ArgsNode; +import org.jruby.ast.CallNode; +import org.jruby.ast.ClassNode; +import org.jruby.ast.ClassVarAsgnNode; +import org.jruby.ast.ClassVarDeclNode; +import org.jruby.ast.ClassVarNode; +import org.jruby.ast.Colon2Node; +import org.jruby.ast.ConstNode; +import org.jruby.ast.DAsgnNode; +import org.jruby.ast.DVarNode; +import org.jruby.ast.DefnNode; +import org.jruby.ast.DefsNode; +import org.jruby.ast.FCallNode; +import org.jruby.ast.GlobalAsgnNode; +import org.jruby.ast.GlobalVarNode; +import org.jruby.ast.InstAsgnNode; +import org.jruby.ast.InstVarNode; +import org.jruby.ast.ListNode; +import org.jruby.ast.LocalAsgnNode; +import org.jruby.ast.LocalVarNode; +import org.jruby.ast.ModuleNode; +import org.jruby.ast.Node; +import org.jruby.ast.ReturnNode; +import org.jruby.ast.SelfNode; +import org.jruby.ast.VCallNode; +import org.rubypeople.rdt.internal.core.parser.RubyParser; +import org.rubypeople.rdt.internal.ti.data.ConstNodeTypeNames; +import org.rubypeople.rdt.internal.ti.util.ClosestSpanningNodeLocator; +import org.rubypeople.rdt.internal.ti.util.INodeAcceptor; +import org.rubypeople.rdt.internal.ti.util.MethodDefinitionLocator; +import org.rubypeople.rdt.internal.ti.util.MethodInvocationLocator; +import org.rubypeople.rdt.internal.ti.util.OffsetNodeLocator; +import org.rubypeople.rdt.internal.ti.util.ScopedNodeLocator; + +public class DataFlowTypeInferrer extends Object implements ITypeInferrer { + private void sysout(String string) { + // false to suppress debug + if ( true ) { + System.out.println(string); + } + } + + private void prettyPrint(Node node) { + sysout( "----------------------------------------\n" + + "Node: " + node.getClass().getSimpleName() + "\n" + + "Source:\n[" + node.getPosition().getStartOffset() + ".." + node.getPosition().getEndOffset() + "]\n" + + source.substring( node.getPosition().getStartOffset(), node.getPosition().getEndOffset() + 1 ) + "\n" + + "----------------------------------------" ); + } + + TypeInferenceHelper helper; + private String source; + private Node rootNode; + + // To detect cycles in dataflow graph + private List<Node> inferNodeStack; + + + public List<ITypeGuess> infer(String source, int offset) { + List<ITypeGuess> guesses = new LinkedList<ITypeGuess>(); + + this.helper = TypeInferenceHelper.Instance(); + this.source = source; + this.rootNode = (new RubyParser()).parse(source); + this.inferNodeStack = new LinkedList<Node>(); + + Node node = OffsetNodeLocator.Instance().getNodeAtOffset(rootNode, offset); + + if ( node == null ) { return null; } + + guesses = inferNodeType(node); + + guesses = redistributeGuessConfidences(guesses); + + return guesses; + } + + /** + * Redistribute the confidence percentages. I.e. if guesses contains three guesses, each at 100%, they will now each be 33%. + * @param guesses Guesses to redistribute + * @return Guesses with confidences redistributes + */ + private List<ITypeGuess> redistributeGuessConfidences( List<ITypeGuess> guesses ) { + int sum = 0; + for ( ITypeGuess guess : guesses ) { + sum += guess.getConfidence(); + } + + List<ITypeGuess> newGuesses = new ArrayList<ITypeGuess>(guesses.size()); + for ( ITypeGuess guess : guesses ) { + ITypeGuess newGuess = new BasicTypeGuess( guess.getType(), (int)(((double)guess.getConfidence()) / ((double)sum) * 100.0 ) ); + newGuesses.add( newGuess ); + } + + return newGuesses; + } + + // Infer the type of specified node + private List<ITypeGuess> inferNodeType(Node node) { + + sysout("Inferring node: " + node.getClass().getSimpleName()); + List<ITypeGuess> guesses = new ArrayList<ITypeGuess>(1); + + // Detect cycles in data flow graph + if ( inferNodeStack.indexOf( node ) != -1 ) { + sysout("Data flow graph cycle detected:"); + prettyPrint(node); + return guesses; + } + + // Push node onto stack + inferNodeStack.add( 0, node ); + + if ( isSelfReferenceNode( node ) ) { + guesses.add( getSelfReferenceNodeType( node ) ); + } + + if ( isAssignmentNode( node ) ) { + guesses.addAll( inferNodeType( getAssignmentNodeValueNode( node ) ) ); + } + + if ( isTypeDefinitionNode( node ) ) { + guesses.add( getTypeDefinitionNodeType( node ) ); + } + + if ( isConstantNode( node ) ) { + guesses.add( getConstantNodeType( node ) ); + } + + if ( node instanceof LocalVarNode ) { + guesses.addAll( getLocalVarReferenceNodeTypes( (LocalVarNode)node ) ); + } + + if ( node instanceof DVarNode ) { + guesses.addAll( getDVarReferenceNodeTypes( (DVarNode)node ) ); + } + + if ( node instanceof InstVarNode ) { + guesses.addAll( getInstanceVarReferenceNodeTypes( (InstVarNode)node ) ); + } + + if ( node instanceof ClassVarNode ) { + guesses.addAll( getClassVarReferenceNodeTypes( (ClassVarNode)node ) ); + } + + if ( node instanceof GlobalVarNode ) { + guesses.addAll( getGlobalVarReferenceNodeTypes( (GlobalVarNode)node ) ); + } + + if ( isCallNode( node ) ) { + guesses.addAll( getCallNodeTypes( node ) ); + } + + +// PSEUDOCODE: +// if ( element is_a(instvar or global)) { +//ALREADY USING THIS: +// types = sum(typeOfEach(getThingsAssignedInto(element, :within => element.lexicalScope))); +// return types if any found; +//CAN STILL FALLBACK TO: +// //otherwise +// usages = list of places where element is passed as a param; +// sameTypedElements = list of elements passed into the same method-param-location element is; +// types = sum(typeOfEach(sameTypedElements)); +// return types if any found; +//CAN STILL FALLBACK TO: +// //otherwise +// methods = list of methods invoked against element; +// types = sum(typesRespondingToAllOfThese); +// return types; +// } +// if ( element is_a(method invocation)) { +//ALREADY USING THIS: +// klass = typeOf(receiver); +// +// // nice special case: check for accessors/mutators +// // hook for "magic" combinations; (class << ActiveRecord::Base).find(*) => ArrayOf[klass], etc. +// +// defNode = findDefinition(receiver,method_name); +// return findReturnedTypesInDefNode(); +// } + + + // Pop node from stack + inferNodeStack.remove(0); + + return guesses; + + } + + private boolean isConstantNode(Node node) { + return ( node instanceof ConstNode ) || ( null != ConstNodeTypeNames.get(node.getClass().getSimpleName() ) ); + } + + // Look up from ConstNodeTypeNames + private ITypeGuess getConstantNodeType(Node node) { + if ( node instanceof ConstNode ) { + return new BasicTypeGuess( ((ConstNode)node).getName(), 100 ); + } else { + return new BasicTypeGuess( ConstNodeTypeNames.get(node.getClass().getSimpleName()), 100 ); + } + } + + private boolean isTypeDefinitionNode(Node node) { + return ( node instanceof ClassNode ) || ( node instanceof ModuleNode ); + } + + private ITypeGuess getTypeDefinitionNodeType(Node node) { + String typeNodeName = helper.getTypeNodeName( node ); + if ( typeNodeName != null ) { + return new BasicTypeGuess( typeNodeName, 100 ); + } + return null; + } + + private boolean isSelfReferenceNode(Node node) { + return ( node instanceof SelfNode); + } + + private ITypeGuess getSelfReferenceNodeType( Node node ) { + Node enclosingTypeNode = findEnclosingTypeNode( node ); + return getTypeDefinitionNodeType( enclosingTypeNode ); + } + + private List<Node> findAllSendersOfMethod( String typeName, String methodName ) { + return MethodInvocationLocator.Instance().findMethodInvocations( rootNode, source, typeName, methodName, new DataFlowTypeInferrer() ); + } + + private List<Node> findAllMethodDefinitions( String typeName, String methodName ) { + return MethodDefinitionLocator.Instance().findMethodDefinitions( rootNode, source, typeName, methodName ); + } + + private List<Node> findRetvalExprs( Node methodNode ) { + + + //TODO: Does this handle implicit returns?? + + List<Node> returnNodes = ScopedNodeLocator.Instance().findNodesInScope(methodNode, new INodeAcceptor() { + public boolean doesAccept(Node node) { + return ( node instanceof ReturnNode ); + } + }); + + List<Node> retvalExprs = new ArrayList<Node>(returnNodes.size()); + for ( Node returnNode : returnNodes ) { + retvalExprs.add( ((ReturnNode)returnNode).getValueNode() ); + } + + sysout("Found " + retvalExprs.size() + " + retval exprs in method " + helper.getMethodDefinitionNodeName( methodNode )); + + return retvalExprs; + } + + private Node findEnclosingMethodNode(Node node) { + Node enclosingScopeNode = ClosestSpanningNodeLocator.Instance().findClosestSpanner(rootNode, node.getPosition().getStartOffset(), new INodeAcceptor() { + public boolean doesAccept(Node node) { + return ( node instanceof DefnNode ) || + ( node instanceof DefsNode ); + } + }); + + if ( enclosingScopeNode == null ) { + enclosingScopeNode = rootNode; + } + + return enclosingScopeNode; + } + + private Node findEnclosingTypeNode(Node node) { + Node enclosingTypeNode = ClosestSpanningNodeLocator.Instance().findClosestSpanner(rootNode, node.getPosition().getStartOffset(), new INodeAcceptor() { + public boolean doesAccept(Node node) { + return ( node instanceof ClassNode ) || ( node instanceof ModuleNode ); + } + }); + + // TODO: Handle reference inside metaclass block: + // class << foo; [[INFER]] ..... + + if ( enclosingTypeNode == null ) { + enclosingTypeNode = rootNode; + } + + return enclosingTypeNode; + } + + private List<ITypeGuess> getLocalVarReferenceNodeTypes(LocalVarNode node) { + List<ITypeGuess> possibleTypes = new ArrayList<ITypeGuess>(1); + + + // Get enclosing scope + Node enclosingScopeNode = findEnclosingMethodNode( node ); + if ( enclosingScopeNode == rootNode ) { + sysout("localvarnode outside a method!"); + enclosingScopeNode = findEnclosingTypeNode( node ); + } + + //TODO: ScopedNodeLocator doesn't ensure that returned asgns are prior to the ref... relevant to algo? + // Are there prior assigns into this ref within the scope? + final String localVarName = helper.getVarName(source, node); + + List<Node> localAssignsIntoNode = ScopedNodeLocator.Instance().findNodesInScope(enclosingScopeNode, new INodeAcceptor() { + public boolean doesAccept(Node acceptNode) { + if ( acceptNode instanceof LocalAsgnNode ) { + return ( ((LocalAsgnNode)acceptNode).getName().equals( localVarName ) ); + } + return false; + } + }); + + // If so, return the sum of the RHSes' type inferences + if ( ( localAssignsIntoNode != null ) && ( localAssignsIntoNode.size() > 0 ) ) { + for ( Node asgnNode : localAssignsIntoNode ) { + possibleTypes.addAll( inferNodeType( ((LocalAsgnNode)asgnNode).getValueNode() ) ); + } + return possibleTypes; + } + + + // No prior assigns; if is an arg, find send-exprs into that arg, return sum of their inferences + if ( helper.isArgumentInMethod( localVarName, enclosingScopeNode ) ) { + + // Rename for clarity + Node enclosingMethodNode = enclosingScopeNode; + + sysout("Is arg in method"); + // Get enclosing type name + Node enclosingTypeNode = findEnclosingTypeNode(node); + String enclosingTypeName = "Kernel"; + if ( enclosingTypeNode != rootNode ) { + enclosingTypeName = helper.getTypeNodeName( enclosingTypeNode ); + } + + // Get enclosing method name + String enclosingMethodName = helper.getMethodDefinitionNodeName( enclosingMethodNode ); + + sysout("Inferring type of argument " + localVarName + " in method " + enclosingMethodName ); + + // Find index of param + ListNode argsListNode = helper.getArgsListNode( enclosingMethodNode ); + int paramIndex = helper.getArgIndex( argsListNode, localVarName ); + + // Find all send-exprs to the enclosing method + List<Node> sendExprs = findAllSendersOfMethod( enclosingTypeName, enclosingMethodName ); + sysout( "Found " + sendExprs.size() + " senders: " ); + + + // Find all arg-exprs in the send-exprs that flow into the local var + List<Node> argExprs = new ArrayList<Node>(sendExprs.size()); + for ( Node sendExpr : sendExprs ) { + prettyPrint(sendExpr); + argExprs.add( helper.findNthArgExprInSendExpr( paramIndex, sendExpr ) ); + } + + sysout("Inflowing argexprs:" + argExprs.size()); + // Sum the inferred type of each arg-exprs that flows into the local var + for ( Node argExpr : argExprs ) { + prettyPrint(argExpr); + possibleTypes.addAll( inferNodeType(argExpr) ); + } + + return possibleTypes; + } + + sysout("bottom"); + + // No prior assigns and is not an arg; return empty set of guesses. + return possibleTypes; + + } + + private List<ITypeGuess> getDVarReferenceNodeTypes(DVarNode node) { + List<ITypeGuess> possibleTypes = new ArrayList<ITypeGuess>(1); + + Node enclosingScopeNode = findEnclosingMethodNode( node ); + if ( enclosingScopeNode == rootNode ) { + enclosingScopeNode = findEnclosingTypeNode( node ); + } + + // Find assignments into this variable + final String varName = node.getName(); + List<Node> dynAsgnNodes = ScopedNodeLocator.Instance().findNodesInScope(enclosingScopeNode, new INodeAcceptor() { + public boolean doesAccept(Node acceptNode) { + if ( acceptNode instanceof DAsgnNode ) { + return ( ((DAsgnNode)acceptNode).getName().equals( varName ) ); + } + return false; + } + }); + + // Sum the inferred type of assignment RHSes + if ( dynAsgnNodes != null ) { + for ( Node dynAsgnNode : dynAsgnNodes ) { + possibleTypes.addAll( inferNodeType( ((DAsgnNode)dynAsgnNode).getValueNode() ) ); + } + } + + return possibleTypes; + } + + private List<ITypeGuess> getInstanceVarReferenceNodeTypes(InstVarNode node) { + List<ITypeGuess> possibleTypes = new ArrayList<ITypeGuess>(1); + + Node enclosingTypeNode = findEnclosingTypeNode( node ); + + // Find assignments into this variable + final String instanceVarName = helper.getVarName(source, node); + List<Node> instAsgnNodes = ScopedNodeLocator.Instance().findNodesInScope(enclosingTypeNode, new INodeAcceptor() { + public boolean doesAccept(Node acceptNode) { + if ( acceptNode instanceof InstAsgnNode ) { + return ( ((InstAsgnNode)acceptNode).getName().equals( instanceVarName ) ); + } + return false; + } + }); + + //TODO: also collect calls to [parentype].instvarname= + + // Sum the inferred type of assignment RHSes + if ( instAsgnNodes != null ) { + for ( Node instAsgnNode : instAsgnNodes ) { + possibleTypes.addAll( inferNodeType( ((InstAsgnNode)instAsgnNode).getValueNode() ) ); + } + } + + return possibleTypes; + } + + private List<ITypeGuess> getClassVarReferenceNodeTypes(ClassVarNode node) { + List<ITypeGuess> possibleTypes = new ArrayList<ITypeGuess>(1); + + Node enclosingTypeNode = findEnclosingTypeNode( node ); + + // Find assignments into this variable + final String classVarName = helper.getVarName(source, node); + prettyPrint(enclosingTypeNode); + List<Node> classAsgnNodes = ScopedNodeLocator.Instance().findNodesInScope(enclosingTypeNode, new INodeAcceptor() { + public boolean doesAccept(Node acceptNode) { + if ( acceptNode instanceof ClassVarAsgnNode ) { + return ( ((ClassVarAsgnNode)acceptNode).getName().equals( classVarName ) ); + } else if ( acceptNode instanceof ClassVarDeclNode ) { + return ( ((ClassVarDeclNode)acceptNode).getName().equals( classVarName ) ); + } + return false; + } + }); + + //TODO: class Klass;@@x=5;@@x=6;@@x;end # @@x=5 is parsed as a ClassDeclNode, and so is @@x=6. Do ClassAsgnNodes ever pop up??? + + + //TODO: also collect calls to [parentypeklass].classvarname= + + // Sum the inferred type of assignment RHSes + if ( classAsgnNodes != null ) { + sysout("asgns not null: " + classAsgnNodes.size()); + for ( Node classAsgnNode : classAsgnNodes ) { + if ( classAsgnNode instanceof ClassVarAsgnNode ) { + possibleTypes.addAll( inferNodeType( ((ClassVarAsgnNode)classAsgnNode).getValueNode() ) ); + } + if ( classAsgnNode instanceof ClassVarDeclNode ) { + possibleTypes.addAll( inferNodeType( ((ClassVarDeclNode)classAsgnNode).getValueNode() ) ); + } + } + } + + return possibleTypes; + } + + private List<ITypeGuess> getGlobalVarReferenceNodeTypes(GlobalVarNode node) { + List<ITypeGuess> possibleTypes = new ArrayList<ITypeGuess>(1); + + // Find assignments into this variable + final String globalVarName = helper.getVarName(source, node); + List<Node> globalAsgnNodes = ScopedNodeLocator.Instance().findNodesInScope(rootNode, new INodeAcceptor() { + public boolean doesAccept(Node acceptNode) { + if ( acceptNode instanceof GlobalAsgnNode ) { + return ( ((GlobalAsgnNode)acceptNode).getName().equals( globalVarName ) ); + } + return false; + } + }); + + // Sum the inferred type of assignment RHSes + for ( Node globalAsgnNode : globalAsgnNodes ) { + possibleTypes.addAll( inferNodeType( ((GlobalAsgnNode)globalAsgnNode).getValueNode() ) ); + } + + return possibleTypes; + } + + + private boolean isAssignmentNode( Node node ) { + return ( node instanceof LocalAsgnNode ) || ( node instanceof InstAsgnNode ) || ( node instanceof GlobalAsgnNode ); + } + + private Node getAssignmentNodeValueNode( Node node ) { + if ( node instanceof InstAsgnNode ) { return ((InstAsgnNode)node).getValueNode(); } + if ( node instanceof LocalAsgnNode ) { return ((LocalAsgnNode)node).getValueNode(); } + if ( node instanceof GlobalAsgnNode ) { return ((GlobalAsgnNode)node).getValueNode(); } + return null; + } + + private boolean isCallNode( Node node ) { + return ( node instanceof CallNode ) || ( node instanceof FCallNode ) || ( node instanceof VCallNode ); + } + + private List<ITypeGuess> getCallNodeTypes( Node node ) { + String methodName = helper.getCallNodeMethodName( node ); + + // Handle class instantiations separately + if ( methodName.equals("new") ) { + return getInstantiationCallNodeTypes( node ); + } + + List<ITypeGuess> possibleTypes = new LinkedList<ITypeGuess>(); + String receiverTypeName = null; + + if ( node instanceof CallNode ) { + List<ITypeGuess> receiverTypeInferences = inferNodeType( ((CallNode)node).getReceiverNode() ); + //TODO Handle all types instead of the first + if ( receiverTypeInferences.size() > 0 ) { + receiverTypeName = receiverTypeInferences.get(0).getType(); + } + + } + if ( node instanceof FCallNode ) { + receiverTypeName = helper.getTypeNodeName(findEnclosingTypeNode( node )); + } + if ( node instanceof VCallNode ) { + + //TODO WTF why doesn't VCallNode support getReceiverNode + receiverTypeName="Kernel"; + } + + //TODO: Find method defnnode, sum types of its retval-exprs + List<Node> defnNodes = findAllMethodDefinitions(receiverTypeName, methodName); + + sysout(" " + defnNodes.size() + " defnnodes found"); + // For each send-expr, collect all retval-exprs + List<Node> retvalExprs = new LinkedList<Node>(); + for ( Node defnNode : defnNodes ) { + retvalExprs.addAll( findRetvalExprs( defnNode ) ); + } + + // Sum possible types for all retval-exprs + for ( Node retvalExpr : retvalExprs ) { + possibleTypes.addAll( inferNodeType( retvalExpr ) ); + } + + return possibleTypes; + } + + private List<ITypeGuess> getInstantiationCallNodeTypes( Node node ) { + List<ITypeGuess> possibleTypes = new ArrayList<ITypeGuess>(1); + + if ( node instanceof CallNode ) { + Node receiverNode = ((CallNode)node).getReceiverNode(); + return inferNodeType( receiverNode ); + } + if ( node instanceof FCallNode ) { + Node enclosingTypeNode = findEnclosingTypeNode(node); + possibleTypes.add( getTypeDefinitionNodeType( enclosingTypeNode ) ); + } + if ( node instanceof VCallNode ) { + System.err.println("//TODO: Why doesn't VCallNode support getReceiverNode() ???"); + //TODO: Why doesn't VCallNode support getReceiverNode() ??? +// Node receiverNode = ((VCallNode)node).getReceiverNode(); +// return inferNodeType( receiverNode ); + } + + return possibleTypes; + } +} Added: branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/TypeInferenceHelper.java =================================================================== --- branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/TypeInferenceHelper.java (rev 0) +++ branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/TypeInferenceHelper.java 2006-08-21 08:30:19 UTC (rev 1576) @@ -0,0 +1,120 @@ +package org.rubypeople.rdt.internal.ti; + +import java.util.Iterator; + +import org.jruby.ast.ArgsNode; +import org.jruby.ast.ArgumentNode; +import org.jruby.ast.ArrayNode; +import org.jruby.ast.CallNode; +import org.jruby.ast.ClassNode; +import org.jruby.ast.ClassVarNode; +import org.jruby.ast.Colon2Node; +import org.jruby.ast.DefnNode; +import org.jruby.ast.DefsNode; +import org.jruby.ast.FCallNode; +import org.jruby.ast.GlobalVarNode; +import org.jruby.ast.InstVarNode; +import org.jruby.ast.ListNode; +import org.jruby.ast.LocalVarNode; +import org.jruby.ast.ModuleNode; +import org.jruby.ast.Node; +import org.jruby.ast.VCallNode; +import org.jruby.lexer.yacc.ISourcePosition; +import org.rubypeople.rdt.internal.ti.util.ScopedNodeLocator; + +public class TypeInferenceHelper { + + //Singleton pattern + private TypeInferenceHelper() {} + private static TypeInferenceHelper staticInstance = new TypeInferenceHelper(); + public static TypeInferenceHelper Instance() { + return staticInstance; + } + + /** + * Extracts the name of a variable from a VarNode + * @param source Source that contains the node + * @param node LocalVarNode, InstVarNode, or GlobalVarNode referring to a variable. + * @return Name of the variable. + */ + public String getVarName(String source, Node node) + { + ISourcePosition pos = null; + if ( node instanceof InstVarNode ) pos = ((InstVarNode)node).getPosition(); + if ( node instanceof ClassVarNode ) pos = ((ClassVarNode)node).getPosition(); + if ( node instanceof LocalVarNode ) pos = ((LocalVarNode)node).getPosition(); + if ( node instanceof GlobalVarNode ) pos = ((GlobalVarNode)node).getPosition(); + if ( pos != null ) + { + return source.substring(pos.getStartOffset(), pos.getEndOffset()+1); + } + return null; + } + + + public int getArgIndex(ListNode listNode, String argName) + { + int argNumber = 0; + for ( Iterator iter = listNode.iterator(); iter.hasNext();) { + if (((ArgumentNode)iter.next()).getName().equals(argName)) { return argNumber; } + argNumber++; + } + return -1; + } + + public String getTypeNodeName( Node node ) { + if ( node instanceof ClassNode ) { return ((Colon2Node)((ClassNode)node).getCPath()).getName(); } + if ( node instanceof ModuleNode ) { return ((Colon2Node)((ModuleNode)node).getCPath()).getName(); } + return null; + } + + public String getMethodDefinitionNodeName(Node methodNode) { + if ( methodNode instanceof DefnNode ) return ((DefnNode)methodNode).getName(); + if ( methodNode instanceof DefsNode ) return ((DefsNode)methodNode).getName(); + return null; + } + + public boolean isArgumentInMethod( String varName, Node enclosingScopeNode ) { + ListNode listNode = getArgsListNode( enclosingScopeNode ); + + // If the args node cannot be located, varName is probably not an arg ;) + if ( listNode == null ) { + return false; + } + + // See if the method contains the variable by name + return ( getArgIndex( listNode, varName ) >= 0 ); + } + + public ListNode getArgsListNode( Node node ) { + if ( node instanceof DefnNode ) { return ((ArgsNode)( ((DefnNode)node).getArgsNode() )).getArgs(); } + if ( node instanceof DefsNode ) { return ((ArgsNode)( ((DefsNode)node).getArgsNode() )).getArgs(); } + if ( node instanceof CallNode ) { return ((ArgsNode)( ((CallNode)node).getArgsNode() )).getArgs(); } + + //TODO: Is ArrayNode the proper cast? + if ( node instanceof FCallNode ) { return (ArrayNode)( ((FCallNode)node).getArgsNode() ); } + // VCallNode is a node w/o args + + return null; + } + + + public String getCallNodeMethodName( Node node ) { + if ( node instanceof CallNode ) { return ((CallNode)node).getName(); } + if ( node instanceof FCallNode ) { return ((FCallNode)node).getName(); } + if ( node instanceof VCallNode ) { return ((VCallNode)node).getMethodName(); } + return null; + } + + public Node findNthArgExprInSendExpr( int n, Node sendExprNode ) { + ListNode listNode = getArgsListNode( sendExprNode ); + if ( listNode == null ) { + return null; + } + + + return listNode.get(n); + } + + +} Modified: branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/util/ClosestSpanningNodeLocator.java =================================================================== --- branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/util/ClosestSpanningNodeLocator.java 2006-08-20 22:06:09 UTC (rev 1575) +++ branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/util/ClosestSpanningNodeLocator.java 2006-08-21 08:30:19 UTC (rev 1576) @@ -4,7 +4,7 @@ import org.jruby.evaluator.Instruction; /** - * Visitor to find the first node that precedes a given offset that satisfies a given condition. + * Visitor to find the closest node that spans a given offset that satisfies a given condition. * @author Jason Morrison */ public class ClosestSpanningNodeLocator extends NodeLocator { @@ -17,13 +17,13 @@ return staticInstance; } - /** Offset to start searching backwards from. */ + /** Offset to span. */ private int offset; /** INodeAcceptor that defines the desired node. */ private INodeAcceptor acceptor; - /** Running best match for closest precursor */ + /** Running best match for closest spanner */ private Node locatedNode; /** Modified: branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/util/MethodDefinitionLocator.java =================================================================== --- branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/util/MethodDefinitionLocator.java 2006-08-20 22:06:09 UTC (rev 1575) +++ branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/util/MethodDefinitionLocator.java 2006-08-21 08:30:19 UTC (rev 1576) @@ -11,10 +11,17 @@ import org.jruby.ast.ArgsNode; import org.jruby.ast.ArgumentNode; import org.jruby.ast.ArrayNode; +import org.jruby.ast.CallNode; +import org.jruby.ast.ClassNode; import org.jruby.ast.DefnNode; import org.jruby.ast.DefsNode; +import org.jruby.ast.FCallNode; +import org.jruby.ast.ModuleNode; import org.jruby.ast.Node; import org.jruby.evaluator.Instruction; +import org.rubypeople.rdt.internal.ti.ITypeGuess; +import org.rubypeople.rdt.internal.ti.ITypeInferrer; +import org.rubypeople.rdt.internal.ti.TypeInferenceHelper; /** * Visitor to find all method definitions within a specific scope. @@ -30,38 +37,88 @@ return staticInstance; } - /** Running total of results; is a Set to ensure uniqueness */ - private Set<String> methods; + /** Inference helper */ + private TypeInferenceHelper helper = TypeInferenceHelper.Instance(); + /** Type of receiver to look for */ + private String typeName; + + /** Name of method to search for invocations of */ + private String methodName; + + /** Stack of names of types (Class/Module) enclosing the visitor cursor as we traverse */ + private List<String> typeNameStack; + + /** Running total of results */ + private List<Node> locatedNodes; + + /** Source to search within */ + private String source; + /** - * Finds all method definitions within a given node - * @param rootNode + * Finds all method definition node within rootNode whose enclosing type is of type typeName and method is named methodName + * @param rootNode Node to search within + * @param source Source to search within + * @param typeName Name of type of method-send-expr receiver + * @param methodName Name of method to find * @return */ - public List<String> findMethodDefinitionsInScope(Node rootNode) { - if ( rootNode == null ) { return new ArrayList<String>(); } + public List<Node> findMethodDefinitions( Node rootNode, String source, String typeName, String methodName ) { + if ( rootNode == null ) { return null; } - methods = new HashSet<String>(); + this.locatedNodes = new LinkedList<Node>(); + this.typeNameStack = new LinkedList<String>(); + this.typeName = typeName; + this.methodName = methodName; + typeNameStack.add("Kernel"); + // Traverse to find all matches rootNode.accept(this); // Return the matches - return new ArrayList<String>(methods); + return locatedNodes; } - /** - * Searches via InOrderVisitor for matches - */ - public Instruction handleNode(Node node ) { - if ( node instanceof DefnNode ) { - methods.add( ((DefnNode)node).getName() ); + + public Instruction handleNode(Node iVisited) { + if ( ( iVisited instanceof DefnNode ) || ( iVisited instanceof DefsNode ) ) { + if ( peekType().equals(typeName)) { + String methodName = helper.getMethodDefinitionNodeName( iVisited ); + if ( methodName.equals(methodName) ) { + locatedNodes.add(iVisited); + } + } } - if ( node instanceof DefsNode ) { - methods.add( ((DefsNode)node).getName() ); - } - - return super.handleNode(node); + return super.handleNode(iVisited); } + + public Instruction visitClassNode(ClassNode iVisited) { + pushType( helper.getTypeNodeName( iVisited ) ); + super.visitClassNode( iVisited ); + popType(); + + return null; + } + + public Instruction visitModuleNode(ModuleNode iVisited) { + pushType( helper.getTypeNodeName( iVisited ) ); + super.visitModuleNode( iVisited ); + popType(); + + return null; + } + + private void pushType( String typeName ) { + typeNameStack.add( 0, typeName ); + } + + private void popType() { + typeNameStack.remove(0); + } + + private String peekType() { + return typeNameStack.get(0); + } } Added: branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/util/MethodInvocationLocator.java =================================================================== --- branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/util/MethodInvocationLocator.java (rev 0) +++ branches/type_inferrence/trunk/org.rubypeople.rdt.core/src/org/rubypeople/rdt/internal/ti/util/MethodInvocationLocator.java 2006-08-21 08:30:19 UTC (rev 1576) @@ -0,0 +1,152 @@ +package org.rubypeople.rdt.internal.ti.util; + +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; + +import javax.xml.transform.Source; + +import org.jruby.ast.ArgsNode; +import org.jruby.ast.ArgumentNode; +import org.jruby.ast.CallNode; +import org.jruby.ast.ClassNode; +import org.jruby.ast.Colon2Node; +import org.jruby.ast.FCallNode; +import org.jruby.ast.ModuleNode; +import org.jruby.ast.Node; +import org.jruby.ast.VCallNode; +import org.jruby.evaluator.Instruction; +import org.rubypeople.rdt.internal.ti.ITypeGuess; +import org.rubypeople.rdt.internal.ti.ITypeInferrer; +import org.rubypeople.rdt.internal.ti.TypeInferenceHelper; + +/** + * Visitor to find all method invocations for the specified type and method names + * @author Jason Morrison + */ +public class MethodInvocationLocator extends NodeLocator { + + //Singleton pattern + private MethodInvocationLocator() {} + private static MethodInvocationLocator staticInstance = new MethodInvocationLocator(); + public static MethodInvocationLocator Instance() + { + return staticInstance; + } + + /** Inference helper */ + private TypeInferenceHelper helper = TypeInferenceHelper.Instance(); + + /** Type of receiver to look for */ + private String typeName; + + /** Name of method to search for invocations of */ + private String methodName; + + /** Stack of names of types (Class/Module) enclosing the visitor cursor as we traverse */ + private List<String> typeNameStack; + + /** Running total of results */ + private List<Node> locatedNodes; + + /** Type inferrer to use when resolving receiver-types */ + private ITypeInferrer inferrer; + + /** Source to search within */ + private String source; + + /** + * Finds all method invocation node within rootNode whose receiver is of type typeName and method is named methodName + * @param rootNode Node to search within + * @param source Source to search within + * @param typeName Name of type of method-send-expr receiver + * @param methodName Name of method to find + * @param inferrer Inferrer to use for resolving receiver-types + * @return + */ + public List<Node> findMethodInvocations( Node rootNode, String source, String typeName, String methodName, ITypeInferrer inferrer ) { + if ( rootNode == null ) { return null; } + + this.locatedNodes = new LinkedList<Node>(); + this.typeNameStack = new LinkedList<String>(); + this.typeName = typeName; + this.methodName = methodName; + this.inferrer = inferrer; + + typeNameStack.add("Kernel"); + + // Traverse to find all matches + rootNode.accept(this); + + // Return the matches + return locatedNodes; + } + + + public Instruction handleNode(Node iVisited) { + + // Check for invocations on self + if ( iVisited instanceof FCallNode ) { + if ( ((FCallNode)iVisited).getName().equals(methodName)) { + if ( peekType().equals(typeName)) { + locatedNodes.add(iVisited); + } + } + } + + // Look for CallNodes where receiver matches typeName and methodName matches method invoked + if ( iVisited instanceof CallNode ) { + if ( helper.getCallNodeMethodName(iVisited).equals(methodName)) { + // TI the receiver + Node receiverNode = ((CallNode)iVisited).getReceiverNode(); + List<ITypeGuess> receiverTypeInferences = inferrer.infer( source, receiverNode.getPosition().getStartOffset()); + + // If the receiver matches desired typeName, add a match! + for ( ITypeGuess inference : receiverTypeInferences ) { + if ( inference.getType().equals( typeName ) ) { + locatedNodes.add( iVisited ); + break; + } + } + } + } + +// if ( iVisited instanceof VCallNode ) { + //TODO: VCallNode does not have getReceiverNode(). + // We don't particularly care for the purpose of finding send-exprs that flow params into args of method-defns, since VCallNodes + // don't send w/ args. But, to make this visitor general-purpose, it would have to support VCallNodes. Consider just renaming the +// } + + return super.handleNode(iVisited); + } + + public Instruction visitClassNode(ClassNode iVisited) { + pushType( helper.getTypeNodeName( iVisited ) ); + super.visitClassNode( iVisited ); + popType(); + + return null; + } + + public Instruction visitModuleNode(ModuleNode iVisited) { + pushType( helper.getTypeNodeName( iVisited ) ); + super.visitModuleNode( iVisited ); + popType(); + + return null; + } + + private void pushType( String typeName ) { + typeNameStack.add( 0, typeName ); + } + + private void popType() { + typeNameStack.remove(0); + } + + private String peekType() { + return typeNameStack.get(0); + } + + +} This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
