001: /*
002: * Author: Chris Seguin
003: *
004: * This software has been developed under the copyleft
005: * rules of the GNU General Public License. Please
006: * consult the GNU General Public License for more
007: * details about use and distribution of this software.
008: */
009: package net.sourceforge.jrefactory.query;
010:
011: import java.util.Enumeration;
012: import net.sourceforge.jrefactory.ast.*;
013:
014: /**
015: * Performs a search on the parse tree to find specific nodes.
016: *
017: *@author Chris Seguin
018: */
019: public class Search {
020: private EqualTree equalTree;
021:
022: /**
023: * Constructor for the Search object
024: */
025: public Search() {
026: equalTree = new EqualTree();
027: }
028:
029: /**
030: * This is the main program for this search. The inputs are the root node
031: * and what it is that we are searching for.
032: *
033: *@param root Description of Parameter
034: *@param lookingFor Description of Parameter
035: *@return Description of the Returned Value
036: */
037: public Found search(Node root, Node lookingFor) {
038: //System.out.println("DEBUG[Search.search] #1");
039: int last = root.jjtGetNumChildren();
040: int lookingForLast = lookingFor.jjtGetNumChildren();
041: if (last >= lookingForLast) {
042: Found result = searchAtLevel(root, lookingFor, last
043: - lookingForLast);
044: if (result != null) {
045: return result;
046: }
047: }
048:
049: for (int ndx = 0; ndx < last; ndx++) {
050: Found found = search(root.jjtGetChild(ndx), lookingFor);
051: if (found != null) {
052: return found;
053: }
054: }
055:
056: return null;
057: }
058:
059: /**
060: * Search at the level we are on. This will search on the level we are at
061: * trying to find the items in the lookingFor node. If it is found, a Found
062: * object is returned.
063: *
064: *@param root Description of Parameter
065: *@param lookingFor Description of Parameter
066: *@param stop Description of Parameter
067: *@return Description of the Returned Value
068: */
069: private Found searchAtLevel(Node root, Node lookingFor, int stop) {
070: //System.out.println("DEBUG[Search.searchAtLevel] #1");
071: for (int ndx = 0; ndx <= stop; ndx++) {
072: Node attempt = root.jjtGetChild(ndx);
073: Node lookingForNode = lookingFor.jjtGetFirstChild();
074: //System.out.println("DEBUG[Search.searchAtLevel] #2 " + attempt.getClass().getName() + " " + lookingForNode.getClass().getName());
075: Boolean same = (Boolean) attempt.jjtAccept(equalTree,
076: lookingForNode);
077: if (same.equals(Boolean.TRUE)
078: && findAll(root, lookingFor, ndx)) {
079: //System.out.println("DEBUG[Search.searchAtLevel] #2");
080: return new Found(root, ndx);
081: }
082: }
083:
084: //System.out.println("DEBUG[Search.searchAtLevel] #3");
085: return null;
086: }
087:
088: /**
089: * Now that we have a guess where to find all the nodes, we do a thorough
090: * search. This function will return true if the other items all are found
091: * as children
092: *
093: *@param root Description of Parameter
094: *@param lookingFor Description of Parameter
095: *@param offset Description of Parameter
096: *@return Description of the Returned Value
097: */
098: private boolean findAll(Node root, Node lookingFor, int offset) {
099: //System.out.println("DEBUG[Search.findAll] #1");
100: for (int ndx = 1; ndx < lookingFor.jjtGetNumChildren(); ndx++) {
101: Node attempt = root.jjtGetChild(ndx + offset);
102: Boolean same = (Boolean) attempt.jjtAccept(equalTree,
103: lookingFor.jjtGetChild(ndx));
104: if (same.equals(Boolean.FALSE)) {
105: //System.out.println("DEBUG[Search.findAll] #2");
106: return false;
107: }
108: }
109:
110: //System.out.println("DEBUG[Search.findAll] #3");
111: return specialCase(root, lookingFor, offset);
112: }
113:
114: /**
115: * Certain node types also have names associated with them. These nodes are
116: * mathematical operations such as * or / and < < or >>. We need to check in
117: * the instance that we have such a node that the names all match up. This
118: * method does that computation.
119: *
120: *@param root Description of Parameter
121: *@param lookingFor Description of Parameter
122: *@param offset Description of Parameter
123: *@return Description of the Returned Value
124: */
125: private boolean specialCase(Node root, Node lookingFor, int offset) {
126: //System.out.println("DEBUG[Search.specialCase] #1");
127: Enumeration enum1 = null;
128: Enumeration enum2 = null;
129: if (root instanceof ASTAdditiveExpression) {
130: enum1 = ((ASTAdditiveExpression) root).getNames();
131: enum2 = ((ASTAdditiveExpression) lookingFor).getNames();
132: } else if (root instanceof ASTEqualityExpression) {
133: enum1 = ((ASTEqualityExpression) root).getNames();
134: enum2 = ((ASTEqualityExpression) lookingFor).getNames();
135: } else if (root instanceof ASTMultiplicativeExpression) {
136: enum1 = ((ASTMultiplicativeExpression) root).getNames();
137: enum2 = ((ASTMultiplicativeExpression) lookingFor)
138: .getNames();
139: } else if (root instanceof ASTRelationalExpression) {
140: enum1 = ((ASTRelationalExpression) root).getNames();
141: enum2 = ((ASTRelationalExpression) lookingFor).getNames();
142: } else if (root instanceof ASTShiftExpression) {
143: enum1 = ((ASTShiftExpression) root).getNames();
144: enum2 = ((ASTShiftExpression) lookingFor).getNames();
145: }
146: //System.out.println("DEBUG[Search.specialCase] #2");
147:
148: // We don't need to special case this node then
149: if (enum1 == null) {
150: return true;
151: }
152:
153: // Skip the unnecessary ones
154: for (int ndx = 0; ndx < offset; ndx++) {
155: enum1.nextElement();
156: }
157: //System.out.println("DEBUG[Search.specialCase] #3");
158:
159: // Compare the names
160: while (enum2.hasMoreElements()) {
161: Object value1 = enum1.nextElement();
162: Object value2 = enum2.nextElement();
163:
164: if (!value1.equals(value2)) {
165: //System.out.println("DEBUG[Search.specialCase] #4");
166: return false;
167: }
168: }
169:
170: // All the names are the same, we are done
171: //System.out.println("DEBUG[Search.specialCase] #5");
172: return true;
173: }
174: }
|