001package jtb.cparser.customvisitor;
002
003import jtb.cparser.syntaxtree.*;
004import jtb.cparser.visitor.*;
005import java.util.*;
006
007/**
008 * Identifies the strings in an C AST
009 */
010
011public class StringFinder extends DepthFirstVisitor {
012
013  //Rules used to identify strings:
014  //1.  A 'char[]' is always a string
015  //2.  A 'string' is always a string
016  //3.  A '*char' is a string if:
017  //     a.  There is an array access on it
018  //     b.  It is an argument to one of the functions in stringFunctions
019  //4.  A **char, *char[], or char[][] are always converted to string arrays
020
021
022
023  //holds the names of the char pointers, char arrays, and strings
024  private ArrayList<String> possibleStrings;
025  //holds the possibleStrings that have been verified as strings
026  private ArrayList<String> actualStrings;
027  //holds the string arrays
028  private ArrayList<String> actualStringMatrices;
029  //map the function name with the string arrays
030  public HashMap<String,ArrayList<String>> stringMatrices = new HashMap<String,ArrayList<String>>();
031  //map the function name with the strings
032  public HashMap<String,ArrayList<String>> functionStringMapping = new HashMap<String,ArrayList<String>>();
033  //holds the names of C functions that indicate a char pointer is a string
034  private static HashMap<String,String> stringFunctions = new HashMap<String,String>();
035
036  static {
037    stringFunctions.put("strcat", "strcat");
038    stringFunctions.put("strchr", "strchr");
039    stringFunctions.put("strcmp", "strcmp");
040    stringFunctions.put("strcoll", "strcoll");
041    stringFunctions.put("strcpy", "strcpy");
042    stringFunctions.put("strlen", "strlen");
043    stringFunctions.put("strncat", "strncat");
044    stringFunctions.put("strncmp", "strncmp");
045    stringFunctions.put("strncpy", "strncpy");
046    stringFunctions.put("strstr", "strstr");
047  }
048
049  public void visit(FunctionDefinition n) {
050    possibleStrings = new ArrayList<String>();
051    actualStrings = new ArrayList<String>();
052    actualStringMatrices = new ArrayList<String>();
053    NodeChoice temp = (NodeChoice) n.f1.f1.f1.nodes.get(0);
054    NodeSequence params = (NodeSequence) temp.choice;
055    //find the strings in the function parameters
056    if (params.nodes.get(1) instanceof ParameterTypeList) {
057      ParameterTypeList list = (ParameterTypeList) params.nodes.get(1);
058      identifyPossibleStrings(list.f0);
059    }
060    super.visit(n);
061    functionStringMapping.put(n.f1.f1.f0.choice.toString(), actualStrings);
062    stringMatrices.put(n.f1.f1.f0.choice.toString(), actualStringMatrices);
063  }
064
065  private void identifyPossibleStrings(ParameterList l) {
066    identifyPossibleString(l.f0);
067    for (int i = 0; i < l.f1.nodes.size(); i++) {
068      NodeSequence curr = (NodeSequence) l.f1.nodes.get(i);
069      identifyPossibleString((ParameterDeclaration)curr.nodes.get(1));
070    }
071  }
072
073  private void identifyPossibleString(ParameterDeclaration p) {
074    NodeSequence seq = (NodeSequence)p.f0.f0.choice;
075    if (seq.nodes.get(0) instanceof TypeSpecifier) {
076      TypeSpecifier ts = (TypeSpecifier)(seq).nodes.get(0);
077      if (p.f1.choice instanceof Declarator) {
078        Declarator d = (Declarator)p.f1.choice;
079        Node maybePointer = (d.f0).node;
080        if (ts.f0.choice.toString().equals("char")) {
081          NodeListOptional nodeList = d.f1.f1;
082          if (nodeList.nodes.size() == 1 && !( maybePointer instanceof Pointer)) {
083            NodeChoice tempChoice = (NodeChoice)nodeList.nodes.get(0);
084            NodeSequence tempNodeSeq = (NodeSequence)tempChoice.choice;
085            if (tempNodeSeq.size() > 0 &&
086                tempNodeSeq.nodes.get(0).toString().equals("[") &&
087                tempNodeSeq.nodes.get(2).toString().equals("]")) {
088              actualStrings.add(d.f1.f0.choice.toString().trim());
089            }
090          }
091          else if (nodeList.nodes.size() == 0 && maybePointer instanceof Pointer) {
092            Pointer temp = (Pointer) maybePointer;
093            if (temp.f1.node == null && temp.f2.node == null) {
094              possibleStrings.add( d.f1.f0.choice.toString().trim());
095            }
096            if (temp.f1.node == null && temp.f2.node != null) {
097              actualStringMatrices.add(d.f1.f0.choice.toString().trim());
098            }
099          }
100          else if (nodeList.nodes.size() == 2 && !(maybePointer instanceof Pointer)) {
101            actualStringMatrices.add(d.f1.f0.choice.toString().trim());
102          }
103          else if (nodeList.nodes.size() == 1 && maybePointer instanceof Pointer) {
104            Pointer temp = (Pointer) maybePointer;
105            if (temp.f1.node == null && temp.f2.node == null) {
106              actualStringMatrices.add(d.f1.f0.choice.toString().trim());
107            }
108          }
109        }
110      }
111    }
112  }
113
114  public void visit(PostfixExpression n) {
115    if (n.f1.nodes.size() > 0) {
116      NodeChoice choice = (NodeChoice) n.f1.nodes.get(0);
117      if (choice.choice instanceof NodeSequence) {
118        NodeSequence seq = (NodeSequence) choice.choice;
119        if (seq.nodes.size() == 3 && seq.nodes.get(0).toString().equals("[") &&
120            seq.nodes.get(2).toString().equals("]")) {
121          if (n.f0.f0.choice instanceof NodeToken) {
122            String name = n.f0.f0.choice.toString();
123            addString(name.trim());
124          }
125        }
126        else if (seq.nodes.get(0).toString().equals("(")) {
127          if (stringFunctions.containsKey(n.f0.f0.choice.toString())) {
128            NodeOptional opt = (NodeOptional)seq.nodes.get(1);
129            ArgumentExpressionList ael = (ArgumentExpressionList) opt.node;
130            Vector<AssignmentExpression> assigns = new Vector<AssignmentExpression>();
131            if (ael!=null) {
132              assigns.add(ael.f0);
133              if (ael.f1.nodes.size() > 0) {
134                for (int i = 0; i < ael.f1.nodes.size(); i++) {
135                  NodeSequence curr = (NodeSequence)ael.f1.nodes.get(i);
136                  for (int j = 0; j < curr.nodes.size(); j++) {
137                    if (j%2 == 1) {
138                      assigns.add((AssignmentExpression)curr.nodes.get(j));
139                    }
140                  }
141                }
142              }
143            }
144            identifyActualStrings(assigns);
145          }
146        }
147      }
148    }
149    super.visit(n);
150  }
151
152
153
154  private void identifyActualStrings(Vector<AssignmentExpression> assigns) {
155    for (int i = 0; i < assigns.size(); i++) {
156      AssignmentExpression curr = assigns.get(i);
157      Node n = ((UnaryExpression)((ConditionalExpression)curr.f0.choice).f0.f0.f0.f0.f0.f0.f0.f0.f0.f0.f0.f0.choice).f0.choice;
158      PostfixExpression tempPFExp = (PostfixExpression) n;
159      if (tempPFExp.f0.f0.choice instanceof NodeToken) {
160        String temp = tempPFExp.f0.f0.choice.toString();
161        addString(temp.trim());
162      }
163    }
164  }
165
166  private void addString(String s) {
167    if (possibleStrings.contains(s) && !(actualStrings.contains(s))) {
168      actualStrings.add(s);
169    }
170  }
171}