0001: /*
0002: * xtc - The eXTensible Compiler
0003: * Copyright (C) 2005-2007 New York University, Thomas Moschny
0004: *
0005: * This program is free software; you can redistribute it and/or
0006: * modify it under the terms of the GNU General Public License
0007: * version 2 as published by the Free Software Foundation.
0008: *
0009: * This program is distributed in the hope that it will be useful,
0010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
0012: * GNU General Public License for more details.
0013: *
0014: * You should have received a copy of the GNU General Public License
0015: * along with this program; if not, write to the Free Software
0016: * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
0017: * USA.
0018: */
0019:
0020: package xtc.xform;
0021:
0022: import java.util.ArrayList;
0023: import java.util.HashMap;
0024: import java.util.Iterator;
0025: import java.util.LinkedList;
0026: import java.util.List;
0027: import java.util.NoSuchElementException;
0028:
0029: import xtc.tree.GNode;
0030: import xtc.tree.Visitor;
0031:
0032: /**
0033: * The query engine. This class' {@link #run} method performs queries
0034: * on abstract syntax trees.
0035: *
0036: * @author Joe Pamer
0037: * @author Laune Harris
0038: * @version $Revision: 1.56 $
0039: */
0040: public class Engine {
0041:
0042: /**
0043: * The inner sequence class.
0044: *
0045: */
0046: static class Sequence<T> extends LinkedList<T> {
0047:
0048: /**
0049: * The flattening iterator class.
0050: *
0051: * A lot of assumptions can be made here because an empty list will never
0052: * be inserted into a sequence.
0053: */
0054: static class FlatIterator<K> implements Iterator<K> {
0055:
0056: /** The stack of iterators to be used. */
0057: private LinkedList<Iterator<K>> iterator_stack;
0058:
0059: /**
0060: * Create a new flat iterator.
0061: *
0062: */
0063: public FlatIterator(Iterator<K> iterator) {
0064: iterator_stack = new LinkedList<Iterator<K>>();
0065: iterator_stack.add(iterator);
0066: }
0067:
0068: /**
0069: * Query to see if there is another object in the collection.
0070: * @return True is there are more objects in collection, false otherwise
0071: */
0072: public boolean hasNext() {
0073: boolean has_next = iterator_stack.getLast().hasNext();
0074: while (true) {
0075: if (has_next) {
0076: break;
0077: } else {
0078: iterator_stack.removeLast();
0079: if (0 == iterator_stack.size()) {
0080: break;
0081: } else {
0082: has_next = iterator_stack.getLast()
0083: .hasNext();
0084: }
0085: }
0086: }
0087:
0088: return has_next;
0089: }
0090:
0091: /**
0092: * Return the next object in the collection.
0093: * @return The next object in the collection
0094: */
0095: @SuppressWarnings("unchecked")
0096: public K next() {
0097: // Will throw an exception on its own
0098: Iterator<K> iterator = iterator_stack.getLast();
0099: K o = iterator.next();
0100: if (o instanceof List) {
0101: //supress warning on this line
0102: iterator = ((List<K>) o).iterator();
0103: o = iterator.next();
0104: iterator_stack.add(iterator);
0105: return o;
0106: } else {
0107: return o;
0108: }
0109: }
0110:
0111: /**
0112: * Remove the last item in the collection.
0113: *
0114: */
0115: public void remove() {
0116: // needs more testing
0117: iterator_stack.getLast().remove();
0118: }
0119: } // end class FlatIterator
0120:
0121: /**
0122: * Add a new item to the sequence, but only if it's not a null list.
0123: * @param o to add to the sequence
0124: * @return True if object was added, false otherwise
0125: */
0126: public boolean add(T o) {
0127: if ((!(o instanceof List)) || (0 != ((List) o).size())) {
0128: return super .add(o);
0129: } else {
0130: return false;
0131: }
0132: }
0133:
0134: /**
0135: * See if the sequence contains a specified object.
0136: * @param oiq The search key
0137: * @return True if the object is in the sequence, false otherwise
0138: */
0139: public boolean contains(Object oiq) {
0140: for (Iterator<T> i = this .iterator(); i.hasNext();) {
0141: Object o = i.next();
0142: if (oiq.equals(o)) {
0143: return true;
0144: }
0145: }
0146: return false;
0147: }
0148:
0149: /**
0150: * Get a new flat iterator over the sequence.
0151: * @return The iterator for the current sequence
0152: */
0153: @SuppressWarnings("unchecked")
0154: public Iterator<Iterator<?>> flatIterator() {
0155: return new FlatIterator(this .iterator());
0156: }
0157: } // end class Sequence
0158:
0159: /**
0160: * The run-time environment of a query.
0161: *
0162: */
0163: static class Environment {
0164:
0165: /**
0166: * Stack frames.
0167: *
0168: */
0169: static class Frame {
0170:
0171: /** The map of variable names to values. */
0172: private HashMap<String, Sequence<Variable>> symbols;
0173:
0174: /**
0175: * Create a new stack frame.
0176: *
0177: */
0178: public Frame() {
0179: symbols = new HashMap<String, Sequence<Variable>>();
0180: }
0181:
0182: /**
0183: * Enter a variable into the stack frame.
0184: * @param name The name of the variable to insert into the stack frame
0185: * @param value The value of the variable to insert into the stack frame
0186: */
0187: @SuppressWarnings("unchecked")
0188: public void setVariable(String name, Sequence<?> value) {
0189: Sequence<Variable> v = (Sequence<Variable>) value;
0190: symbols.put(name, v);
0191: }
0192:
0193: /**
0194: * Get a variable.
0195: * @param name The name of the variable to return
0196: * @return The Sequence of variables that match the name specified
0197: */
0198: public Sequence<Variable> getVariable(String name) {
0199: return symbols.get(name);
0200: }
0201:
0202: } // end class Frame
0203:
0204: /** A query's stack as a list of stack frames. */
0205: private LinkedList<Frame> stack_frames;
0206:
0207: /** The focus of a query's path expressions. */
0208: private LinkedList<Sequence<?>> focus_stack;
0209:
0210: /**
0211: * Create a new environment.
0212: *
0213: */
0214: public Environment() {
0215: stack_frames = new LinkedList<Frame>();
0216: focus_stack = new LinkedList<Sequence<?>>();
0217: }
0218:
0219: /**
0220: * Push a new stack frame.
0221: *
0222: */
0223: public void pushScope() {
0224: stack_frames.add(new Frame());
0225: }
0226:
0227: /**
0228: * Pop the current stack frame.
0229: *
0230: */
0231: public void popScope() {
0232: if (!(0 == stack_frames.size())) {
0233: stack_frames.removeLast();
0234: }
0235: }
0236:
0237: /**
0238: * Fetch a variable from the environment's stack.
0239: * @param name The name of the stack variable to return
0240: * @return The list of variables that match the name specified
0241: */
0242: public Sequence<Variable> getVariable(String name) {
0243: int nframe = stack_frames.size() - 1;
0244: Sequence<Variable> value = null;
0245:
0246: while (nframe >= 0) {
0247: value = (stack_frames.get(nframe)).getVariable(name);
0248: if (null != value) {
0249: break;
0250: } else {
0251: nframe--;
0252: }
0253: }
0254: return value;
0255: }
0256:
0257: /**
0258: * Store a variable in the current stack frame.
0259: * @param name The name of the variable to add to the current stack frame
0260: * @param value The value of the variable to add to the current stack frame
0261: */
0262: @SuppressWarnings("unchecked")
0263: public void setVariable(String name, Sequence<?> value) {
0264: Sequence<Variable> v = (Sequence<Variable>) value;
0265: if (0 == stack_frames.size())
0266: pushScope();
0267: stack_frames.getLast().setVariable(name, v);
0268: }
0269:
0270: /**
0271: * Push a focus.
0272: * @param focus The focus to add to the focus stack
0273: */
0274: public void pushFocus(Sequence<?> focus) {
0275: focus_stack.add(focus);
0276: }
0277:
0278: /**
0279: * Pop a focus.
0280: * @return The focus on top of the focus stack
0281: */
0282: public Sequence<?> popFocus() throws NoSuchElementException {
0283: Sequence<?> l = focus_stack.getLast();
0284: focus_stack.removeLast();
0285: return l;
0286: }
0287:
0288: /**
0289: * Peek at the current focus.
0290: * @return the focus on top of the focus stack
0291: */
0292: public Sequence<?> peekFocus() throws NoSuchElementException {
0293: return focus_stack.getLast();
0294: }
0295:
0296: } // end class Environment
0297:
0298: /**
0299: * Models a query variable as a name/value pair.
0300: *
0301: */
0302: static class Variable {
0303:
0304: /** The name of the variable. */
0305: String name;
0306:
0307: /** The value of the variable. */
0308: Sequence<?> value;
0309:
0310: /**
0311: * Create a new variable.
0312: * @param name The name of the variable to be create
0313: * @param value The value of the variable to be created
0314: */
0315: public Variable(String name, Sequence<?> value) {
0316: this .name = name;
0317: this .value = value;
0318: }
0319:
0320: /**
0321: * Print the variable name and value.
0322: *
0323: */
0324: public String toString() {
0325: return name + " : " + value;
0326: }
0327:
0328: } // end class Variable
0329:
0330: /** Flag for root-relative expression evaluation. */
0331: final int FOCUS_ROOT = 0;
0332:
0333: /** Flag for all-nodes-relative expression evaluation. */
0334: final int FOCUS_ALL = 1;
0335:
0336: /** Flag for expression evaluation with an implicit focus. */
0337: final int FOCUS_IMPLICIT = 3;
0338:
0339: /** Flag for continuing focus. */
0340: final int FOCUS_LAST = 4;
0341:
0342: /** Flag for inside-out tree traversal. */
0343: final int FOCUS_INSIDE_OUT = 5;
0344:
0345: /** The focus flag. */
0346: int focus_flag;
0347:
0348: /** The tree modification flag. */
0349: boolean modified_flag = false;
0350:
0351: /** The flag to see if we have to generate another BFS traversal. */
0352: boolean bad_breadth_flag = true;
0353:
0354: /** The BFS data. */
0355: Sequence<?> bfs_sequence;
0356:
0357: /** The query's run-time environmnt. */
0358: Environment environment;
0359:
0360: /** The AST to be transformed or queried. */
0361: GNode source_ast;
0362:
0363: /** The intermediate representation of the source tree. */
0364: Item item_tree;
0365:
0366: /** The query AST's visitor. */
0367: QueryVisitor visitor;
0368:
0369: /** The query's function library. */
0370: HashMap<String, Function> function_table;
0371:
0372: /** The built in library functions */
0373: String[] lib_funcs = { "CountFunction", "LinesFunction",
0374: "LastFunction", "EmptyFunction", "TestFunction",
0375: "IsNullFunction", "SubsequenceFunction", "ConcatFunction",
0376: "UpperCaseFunction", "LowerCaseFunction",
0377: "SubStringFunction" };
0378:
0379: /**
0380: * Create a new engine.
0381: *
0382: */
0383: public Engine() {
0384: environment = null;
0385: visitor = new QueryVisitor();
0386: function_table = new HashMap<String, Function>();
0387: //add the built in library functions to the function table
0388: String class_name = "";
0389: for (int i = 0; i < lib_funcs.length; i++) {
0390: class_name = lib_funcs[i];
0391: try {
0392: Class<?> class_definition = Class.forName("xtc.xform."
0393: + class_name);
0394: Object function_object = class_definition.newInstance();
0395: addFunction((Function) function_object);
0396: } catch (Exception e) {
0397: String msg = "Error: Unable to load class \""
0398: + class_name + "\".";
0399: throw new RuntimeException(msg);
0400: }
0401: }
0402: }
0403:
0404: /**
0405: * Add a function to the engine's function library.
0406: * @param function The external function to add to function library
0407: */
0408: protected void addFunction(Function function) {
0409: function_table.put(function.getName(), function);
0410: }
0411:
0412: /**
0413: * Call the specified function in the engine's function library.
0414: *
0415: * @param name The name of the function.
0416: * @param args The function's arguments.
0417: * @throws IllegalArgumentException Signals that the specified function
0418: * cannot found in the function library.
0419: */
0420: protected Object callFunction(String name, ArrayList<Object> args)
0421: throws IllegalArgumentException {
0422:
0423: Function function = function_table.get(name);
0424:
0425: if (null == function) {
0426: throw new IllegalArgumentException();
0427: } else {
0428: return function.apply(args);
0429: }
0430: }
0431:
0432: /**
0433: * Perform a query on an AST.
0434: *
0435: * @param query The query.
0436: * @param ast The AST to be queried.
0437: * @return The result of the query.
0438: */
0439: public List<Object> run(Query query, GNode ast) {
0440: // initialize the environment
0441: environment = new Environment();
0442: environment.pushScope();
0443: source_ast = ast;
0444: item_tree = genItemTree(source_ast, null, 0);
0445:
0446: // return the result of the query
0447: return createObjectList(castToSequenceOfItem(visitor
0448: .dispatch(query.ast)));
0449: }
0450:
0451: /**
0452: * Turn the list of items into a list of tree items.
0453: * @param item_list The list of items
0454: * @return List of tree items
0455: */
0456: private List<Object> createObjectList(List<Item> item_list) {
0457: ArrayList<Object> object_list = new ArrayList<Object>(item_list
0458: .size());
0459: Iterator<Item> val_it = item_list.iterator();
0460:
0461: while (val_it.hasNext()) {
0462: Object o = val_it.next();
0463:
0464: if (o instanceof List) {
0465: List<Item> temp = new ArrayList<Item>();
0466: temp.addAll(castToSequenceOfItem(o));
0467:
0468: object_list.add(createObjectList(temp));
0469: } else {
0470: object_list.add(((Item) o).object);
0471: }
0472: }
0473:
0474: return object_list;
0475: }
0476:
0477: /**
0478: * Get the root of the source AST.
0479: *
0480: * @return The (possibly transformed) source AST.
0481: */
0482: public GNode getASTRoot() {
0483: return modified_flag ? (GNode) genFinalTree(item_tree)
0484: : source_ast;
0485: }
0486:
0487: /**
0488: * Build a new tree out of item objects.
0489: * @param root The root
0490: * @param parent
0491: * @param index
0492: * @return The tree of item objects
0493: */
0494: private Item genItemTree(Object root, Item parent, int index) {
0495: Item root_item = new Item(root, parent, index);
0496:
0497: if (root instanceof GNode) {
0498: int child_index = 0;
0499: for (Iterator<Object> child_iterator = ((GNode) root)
0500: .iterator(); child_iterator.hasNext(); child_index++) {
0501:
0502: root_item.addChild(genItemTree(child_iterator.next(),
0503: root_item, child_index));
0504: }
0505: }
0506:
0507: return root_item;
0508: }
0509:
0510: /**
0511: * Build the final tree.
0512: *
0513: */
0514: private Object genFinalTree(Item root) {
0515: Object object = root.object;
0516:
0517: if (object instanceof GNode) {
0518: object = GNode.create(((GNode) object).getName());
0519: if (null != root.children) {
0520: for (Iterator<Item> child_iterator = root.children
0521: .iterator(); child_iterator.hasNext();) {
0522:
0523: ((GNode) object).add(genFinalTree(child_iterator
0524: .next()));
0525: }
0526: }
0527: }
0528:
0529: return object;
0530: }
0531:
0532: /** Visistor to evaluate a query over the source AST. */
0533: class QueryVisitor extends Visitor {
0534:
0535: /**
0536: * Visit the specified XForm node.
0537: *
0538: * @param xform The XForm node.
0539: * @return The value of the XForm expression.
0540: */
0541: public List<?> visitXForm(GNode xform) {
0542:
0543: if (0 == xform.size()) {
0544: return new ArrayList<Object>();
0545: }
0546:
0547: // Load external functions
0548: GNode import_node = (GNode) xform.get(0);
0549: if (null != import_node) {
0550: dispatch(import_node);
0551: }
0552:
0553: // return value of the query
0554: return (List<?>) dispatch((GNode) xform.get(1));
0555: }
0556:
0557: /**
0558: * Visit the specified import statement.
0559: *
0560: * @param statement The import statement node.
0561: */
0562: public void visitImportStatement(GNode statement) {
0563: String class_name = "";
0564:
0565: for (Iterator<Object> class_iterator = statement.iterator(); class_iterator
0566: .hasNext();) {
0567:
0568: try {
0569:
0570: GNode class_node = (GNode) class_iterator.next();
0571: class_name = (String) ((Item) dispatch(class_node)).object;
0572:
0573: Class<?> class_definition = Class
0574: .forName(class_name);
0575: Object function_object = class_definition
0576: .newInstance();
0577:
0578: addFunction((Function) function_object);
0579: } catch (Exception e) {
0580: String msg = "Error: Unable to load class \""
0581: + class_name + "\".";
0582: throw new RuntimeException(msg);
0583: }
0584: }
0585: }
0586:
0587: /**
0588: * Visit the specified compound expression node.
0589: *
0590: * @param expression The compound expression node.
0591: * @return The value of the compound expression.
0592: */
0593: public Sequence<?> visitCompoundExpression(GNode expression) {
0594: Sequence<Sequence<?>> value = new Sequence<Sequence<?>>();
0595: int pushes = 0;
0596:
0597: //evaluate each of the compound expression's children
0598: for (Iterator<Object> exp_iterator = expression.iterator(); exp_iterator
0599: .hasNext();) {
0600:
0601: Sequence<?> cur_val = (Sequence<?>) dispatch((GNode) exp_iterator
0602: .next());
0603: value.add(cur_val);
0604: environment.pushFocus(cur_val);
0605: pushes++;
0606: }
0607:
0608: // pop off all of the new focii
0609: while (0 != pushes) {
0610: environment.popFocus();
0611: pushes--;
0612: }
0613:
0614: // return the value of the compound expression
0615: return value;
0616: }
0617:
0618: /**
0619: * Visit the specified let expression.
0620: *
0621: * @param expression The let expression node.
0622: * @return The value of the expression.
0623: */
0624: public Sequence<?> visitLetExpression(GNode expression) {
0625: // enter a new scope
0626: environment.pushScope();
0627:
0628: // set the let bindings
0629: dispatch((GNode) expression.get(0));
0630:
0631: // get the result of its return value using the bindings above
0632: Sequence<?> return_value = (Sequence<?>) dispatch((GNode) expression
0633: .get(1));
0634:
0635: // reenter the previous scope
0636: environment.popScope();
0637:
0638: // return the resultant sequence
0639: return return_value;
0640: }
0641:
0642: /**
0643: * Visit the specified let-binding list, and enter each of its bound
0644: * variables into the symbol table.
0645: *
0646: * @param binding_list The let binding list node.
0647: */
0648: public void visitLetBindingList(GNode binding_list) {
0649:
0650: // bind each sequence to a variable name
0651: for (Iterator<Object> binding_iterator = binding_list
0652: .iterator(); binding_iterator.hasNext();) {
0653:
0654: dispatch((GNode) binding_iterator.next());
0655: }
0656: }
0657:
0658: /**
0659: * Visit the specified let-binding and enter its variable
0660: * into the symbol table.
0661: *
0662: * @param let_binding The let binding node.
0663: */
0664: public void visitLetBinding(GNode let_binding) {
0665:
0666: // extract the name of the variable
0667: GNode varref_node = (GNode) let_binding.get(0);
0668: String name = (String) varref_node.get(0);
0669:
0670: // determine the variable's value
0671: Sequence<Variable> value = new Sequence<Variable>();
0672:
0673: List<?> temp = (List<?>) dispatch((GNode) let_binding
0674: .get(1));
0675:
0676: for (Iterator<?> iter = temp.iterator(); iter.hasNext();) {
0677: value.add((Variable) iter.next());
0678: }
0679:
0680: // bind the value to the name in the symbol table
0681: environment.setVariable(name, value);
0682: }
0683:
0684: /**
0685: * Visit the specified for-expression.
0686: *
0687: * @param expression The for expression node.
0688: * @return The semantic value of the for expression.
0689: */
0690: public Sequence<?> visitForExpression(GNode expression) {
0691:
0692: // enter a new scope
0693: environment.pushScope();
0694:
0695: // get the list of bound variables
0696: ArrayList<Object> variable_list = new ArrayList<Object>();
0697:
0698: variable_list.addAll((List<?>) (dispatch((GNode) expression
0699: .get(0))));
0700:
0701: // create a list of iterators - one for each variable
0702: int numVars = variable_list.size();
0703: ArrayList<Iterator<?>> iterators = new ArrayList<Iterator<?>>(
0704: numVars);
0705:
0706: // initialize the return sequence
0707: Sequence<Sequence<?>> value = new Sequence<Sequence<?>>();
0708:
0709: // store a value-iterator and its first value for each variable
0710: for (int i = 0; i < numVars; i++) {
0711: Iterator<?> value_iterator = ((Variable) variable_list
0712: .get(i)).value.flatIterator();
0713: iterators.add(value_iterator);
0714: if (value_iterator.hasNext()) {
0715: setVariable((Variable) variable_list.get(i),
0716: value_iterator.next());
0717: } else {
0718: // no value sequence for this var, thus empty result
0719: environment.popScope();
0720: return value;
0721: }
0722: }
0723:
0724: // generate the return value, and iterate the variable values
0725: while (true) {
0726: value
0727: .addAll(castToListOfSequence(dispatch((GNode) expression
0728: .get(1))));
0729:
0730: for (int i = numVars - 1; i >= 0; --i) {
0731: Iterator<?> value_iterator = iterators.get(i);
0732: if (value_iterator.hasNext()) {
0733: setVariable((Variable) variable_list.get(i),
0734: value_iterator.next());
0735: break;
0736: }
0737: if (i == 0) {
0738: environment.popScope();
0739: return value;
0740: }
0741: // reset and store iterator for var #i and its first value
0742: value_iterator = ((Variable) variable_list.get(i)).value
0743: .flatIterator();
0744: iterators.set(i, value_iterator);
0745: setVariable((Variable) variable_list.get(i),
0746: value_iterator.next());
0747: }
0748: }
0749: }
0750:
0751: private <T> void setVariable(Variable v, T value) {
0752: Sequence<Object> current_value = new Sequence<Object>();
0753: current_value.add(value);
0754: environment.setVariable(v.name, current_value);
0755: }
0756:
0757: /**
0758: * Visit the specified cfor expression node.
0759: *
0760: * @param expression The cfor expression node.
0761: * @return The semantic value of the expression.
0762: */
0763: public Sequence<?> visitCForExpression(GNode expression) {
0764: // enter a new scope
0765: environment.pushScope();
0766:
0767: // get the list of for variables
0768: ArrayList<?> variable_list = (ArrayList<?>) dispatch((GNode) expression
0769: .get(0));
0770:
0771: // create a list of iterators - one for each variable
0772: ArrayList<Iterator<?>> iterators = new ArrayList<Iterator<?>>(
0773: variable_list.size());
0774:
0775: // initialize the return sequence
0776: Sequence<Sequence<?>> value = new Sequence<Sequence<?>>();
0777:
0778: // set the initial values for the bound variables
0779: for (int i = 0; i < variable_list.size(); i++) {
0780: Variable v = (Variable) variable_list.get(i);
0781: iterators.add(v.value.flatIterator());
0782: }
0783:
0784: // generate the return value, and update the bound variables
0785: while (true) {
0786: //update variable values
0787: for (int i = 0; i < iterators.size(); i++) {
0788: Iterator<?> value_iterator = iterators.get(i);
0789:
0790: if (value_iterator.hasNext()) {
0791: Sequence<Object> current_value = new Sequence<Object>();
0792: current_value.add(value_iterator.next());
0793: Variable v = (Variable) variable_list.get(i);
0794: environment.setVariable(v.name, current_value);
0795:
0796: } else { // one's empty, so we're done
0797: environment.popScope();
0798: return value;
0799: }
0800: }
0801: //concatenate the resulting sequences
0802: value
0803: .addAll(castToListOfSequence(dispatch((GNode) expression
0804: .get(1))));
0805: }
0806: }
0807:
0808: /**
0809: * Visit the specified iterative binding list node.
0810: *
0811: * @param binding_list The iterative binding list node.
0812: * @return The variables bound.
0813: */
0814: public ArrayList<Object> visitIterativeBindingList(
0815: GNode binding_list) {
0816:
0817: // initialize the variable list
0818: ArrayList<Object> variables = new ArrayList<Object>();
0819:
0820: // create a list of variable names coupled with sequences
0821: for (Iterator<Object> bindings = binding_list.iterator(); bindings
0822: .hasNext();) {
0823: variables.add(dispatch((GNode) bindings.next()));
0824: }
0825:
0826: return variables;
0827: }
0828:
0829: /**
0830: * Visit the specified iterative binding.
0831: *
0832: * @param it_binding The iterative binding list node.
0833: * @return The variable bound.
0834: */
0835: public Variable visitIterativeBinding(GNode it_binding) {
0836: // couple a variable name with a sequence
0837: return new Variable((String) ((GNode) it_binding.get(0))
0838: .get(0), (Sequence) dispatch((GNode) it_binding
0839: .get(1)));
0840: }
0841:
0842: /**
0843: * Visit the specified removal
0844: * @param expression The reference nodes for insertions
0845: * @return A sequence constaining the inserted nodes
0846: */
0847: public Sequence<?> visitRemoveExpression(GNode expression) {
0848: modified_flag = true;
0849: bad_breadth_flag = true;
0850: Sequence<?> targets = (Sequence<?>) dispatch((GNode) (expression
0851: .get(0)));
0852:
0853: for (Iterator<?> target_iterator = targets.flatIterator(); target_iterator
0854: .hasNext();) {
0855:
0856: Item target = (Item) target_iterator.next();
0857: Item parent = target.parent;
0858:
0859: if (null == parent) {
0860: throw new RuntimeException(
0861: "Error: can't remove tree root");
0862: } else {
0863: int index = target.index;
0864: parent.removeChild(index);
0865: }
0866: }
0867: return targets;
0868: }
0869:
0870: /**
0871: * Visit the specified addition
0872: * @param expression The reference nodes for additions
0873: * @return A sequence constaining the modified nodes
0874: */
0875: public Sequence<?> visitAddExpression(GNode expression) {
0876: modified_flag = true;
0877: bad_breadth_flag = true;
0878:
0879: Sequence<?> targets = (Sequence<?>) dispatch((GNode) (expression
0880: .get(1)));
0881:
0882: if (targets.isEmpty()) {
0883: return targets;
0884: }
0885: Sequence<Item> added = new Sequence<Item>();
0886: Sequence<?> additions = (Sequence<?>) dispatch((GNode) (expression
0887: .get(0)));
0888:
0889: for (Iterator<?> targetIter = targets.flatIterator(); targetIter
0890: .hasNext();) {
0891: Item target = (Item) targetIter.next();
0892: for (Iterator<?> addIter = additions.flatIterator(); addIter
0893: .hasNext();) {
0894: Item addition = (Item) addIter.next();
0895: target.addChild(addition);
0896: added.add(target);
0897: }
0898: }
0899: return added;
0900: }
0901:
0902: /**
0903: * Visit the specified replacement.
0904: *
0905: * @param expression The replacement node.
0906: * @return A sequence containing only the root of the source AST.
0907: */
0908: public Sequence<Item> visitReplacementExpression(
0909: GNode expression) {
0910: // search out the items to replace
0911: Sequence<Item> targets = castToSequenceOfItem(dispatch((GNode) (expression
0912: .get(0))));
0913:
0914: if (targets.isEmpty()) {
0915: return targets;
0916: } else {
0917: // get the replacement sequence
0918: Sequence<Item> replacements = castToSequenceOfItem(dispatch((GNode) (expression
0919: .get(1))));
0920: return replace(targets, replacements);
0921: }
0922: }
0923:
0924: /**
0925: * Visit the specified insertion
0926: * @param expression The reference nodes for insertions
0927: * @return A sequence constaining the inserted nodes
0928: */
0929: public Sequence<?> visitInsertBeforeExpression(GNode expression) {
0930: return insert(expression, true);
0931: }
0932:
0933: /**
0934: * Visit the specified insertion
0935: * @param expression The reference nodes for insertions
0936: * @return A sequence constaining the inserted nodes
0937: */
0938: public Sequence<?> visitInsertAfterExpression(GNode expression) {
0939: return insert(expression, false);
0940: }
0941:
0942: /**
0943: * Replace each item in a list of targets with one or more replacement
0944: * items. A singleton containing the root node of the source AST is
0945: * returned.
0946: * @param targets The sequence of items to replace
0947: * @param replacements The sequence of replacement items
0948: * @return The sequence of replacement items
0949: */
0950: private Sequence<Item> replace(Sequence<Item> targets,
0951: Sequence<Item> replacements) {
0952: modified_flag = true;
0953: bad_breadth_flag = true;
0954:
0955: Sequence<Item> replaced = new Sequence<Item>();
0956:
0957: for (Iterator<?> target_iterator = targets.flatIterator(); target_iterator
0958: .hasNext();) {
0959:
0960: Item target = (Item) target_iterator.next();
0961: Item parent = target.parent;
0962:
0963: if (null == parent) {
0964: // only for replacing the root
0965: if (1 < replacements.size()) {
0966: throw new RuntimeException(
0967: "Error: Tree root can only be replaced"
0968: + " by a single item.");
0969: } else {
0970: item_tree = replacements.get(0);
0971: replaced.add(item_tree);
0972: }
0973: } else {
0974: int index = target.index;
0975:
0976: // if there's just one item to pop in, we can do the replacement
0977: // a lot faster
0978: if (1 == replacements.size()) {
0979: Item replacement_item = replacements.get(0);
0980: parent.replaceChild(index, replacement_item);
0981: replaced.add(replacement_item);
0982: } else {
0983: // some shifting is in order
0984: parent.replaceChild(index, replacements);
0985: replaced.addAll(replacements);
0986: }
0987: }
0988: }
0989:
0990: return replacements;
0991: }
0992:
0993: /*
0994: * Insert
0995: * @param position True indicate before, False indicates after
0996: * @param expression The insertion node
0997: * @return The list of inserted nodes
0998: *
0999: */
1000: private Sequence<?> insert(GNode expression, boolean position) {
1001: modified_flag = true;
1002: bad_breadth_flag = true;
1003:
1004: Sequence<?> targets = (Sequence<?>) dispatch((GNode) (expression
1005: .get(1)));
1006:
1007: if (targets.isEmpty()) {
1008: return targets;
1009: }
1010: Sequence<Item> insertions = new Sequence<Item>();
1011:
1012: for (Iterator<?> targetIter = targets.flatIterator(); targetIter
1013: .hasNext();) {
1014: Item target = (Item) targetIter.next();
1015: Item parent = target.parent;
1016:
1017: if (null == parent) {
1018: throw new RuntimeException(
1019: "Error: Can't insert before tree root");
1020: } else {
1021: int index = target.index;
1022: if (position) {
1023: insertions = new Sequence<Item>();
1024: insertions
1025: .addAll(castToSequenceOfItem(dispatch((GNode) (expression
1026: .get(0)))));
1027: insertions.add(target);
1028: parent.replaceChild(index, insertions);
1029: } else {
1030: insertions = new Sequence<Item>();
1031: insertions.add(target);
1032: insertions
1033: .addAll(castToSequenceOfItem(dispatch((GNode) (expression
1034: .get(0)))));
1035: parent.replaceChild(index, insertions);
1036: }
1037: }
1038: }
1039: return insertions;
1040: }
1041:
1042: /**
1043: * Visit an if expression.
1044: *
1045: * @param expression The if expression node.
1046: * @return The value of the expression.
1047: */
1048: public Sequence<?> visitIfExpression(GNode expression) {
1049: // resolve the conditional
1050: Sequence<?> conditional = (Sequence<?>) dispatch((GNode) expression
1051: .get(0));
1052:
1053: // if it's not null, resolve child 0, otherwise 1
1054: if (!conditional.isEmpty()) {
1055: return (Sequence<?>) dispatch((GNode) expression.get(1));
1056: } else {
1057: return (Sequence<?>) dispatch((GNode) expression.get(2));
1058: }
1059: }
1060:
1061: /**
1062: * Visit the specified new-item expression.
1063: *
1064: * @param expression The new-item expression.
1065: * @return The new item as a singleton.
1066: */
1067: public Sequence<Item> visitNewItemExpression(GNode expression) {
1068: // wrap the item in a list
1069: Sequence<Item> item_wrapper = new Sequence<Item>();
1070: item_wrapper
1071: .add((Item) dispatch((GNode) expression.get(0)));
1072:
1073: // return the wrapped item
1074: return item_wrapper;
1075: }
1076:
1077: /**
1078: * Visit the specified new-node expression.
1079: *
1080: * @param expression The new-node expression node.
1081: * @return The new node as a singleton.
1082: */
1083: public Item visitNewNodeExpression(GNode expression) {
1084: // grab the name for the node
1085: GNode new_node = GNode
1086: .create((String) dispatch((GNode) expression.get(0)));
1087: Item item = new Item(new_node, null, 0);
1088:
1089: //add the children nodes to the template
1090: Sequence<?> children = (Sequence<?>) dispatch((GNode) expression
1091: .get(1));
1092: Iterator<?> child_iterator = children.flatIterator();
1093: for (; child_iterator.hasNext();) {
1094: Item it = new Item((Item) child_iterator.next());
1095: item.addChild(it);
1096: new_node.add(it.getObject());
1097: }
1098: return item;
1099: }
1100:
1101: /**
1102: * Visit the specified children.
1103: *
1104: * @param children_node The children node.
1105: * @return A list of child nodes.
1106: */
1107: public Sequence<Object> visitChildren(GNode children_node) {
1108: // initialize child list
1109: Sequence<Object> child_list = new Sequence<Object>();
1110:
1111: // gather the children
1112: for (Iterator<Object> child_iterator = children_node
1113: .iterator(); child_iterator.hasNext();) {
1114:
1115: GNode child_node = (GNode) child_iterator.next();
1116:
1117: if (!child_node.isEmpty()) {
1118: Object child_object = dispatch((GNode) child_node
1119: .get(0));
1120: if (child_object instanceof List) {
1121: child_list.addAll((List<?>) child_object);
1122: } else {
1123: child_list.add(child_object);
1124: }
1125: }
1126: }
1127:
1128: return child_list;
1129: }
1130:
1131: /**
1132: * Visit a null expression.
1133: *
1134: * @param null_node The null node.
1135: * @return An item with a null value.
1136: */
1137: public Item visitNull(GNode null_node) {
1138: // simply return a null object
1139: return new Item(null, null, 0);
1140: }
1141:
1142: /**
1143: * Visit the specified string literal.
1144: *
1145: * @param s The string literal node.
1146: * @return The the node.
1147: */
1148: public Item visitStringLiteral(GNode s) {
1149: // return its string child - whether it be a quoted string or a decimal
1150: // note that we're stripping the quotation-marks from the string
1151: String string = s.getString(0).substring(1,
1152: s.getString(0).length() - 1);
1153: return new Item(string, null, 0);
1154: }
1155:
1156: /**
1157: * Visit the specified path expression.
1158: *
1159: * @param path_expression The path expression node.
1160: * @return The value of the path expression.
1161: */
1162: public Sequence<?> visitPathExpression(GNode path_expression) {
1163: if (1 == path_expression.size()) {
1164: focus_flag = FOCUS_IMPLICIT;
1165: // return the result of its relative path expression
1166: return (Sequence<?>) dispatch((GNode) path_expression
1167: .get(0));
1168: } else {
1169: // grab the path-modifier
1170: String focus_modifier = (String) path_expression.get(0);
1171: if ((null != focus_modifier)
1172: && ("/".equals(focus_modifier))) {
1173: focus_flag = FOCUS_ROOT;
1174: return (Sequence<?>) dispatch((GNode) path_expression
1175: .get(1));
1176: } else {
1177: if (null == focus_modifier) {
1178: focus_flag = FOCUS_ALL;
1179: } else { // inside_out
1180: focus_flag = FOCUS_INSIDE_OUT;
1181: }
1182: return (Sequence<?>) dispatch((GNode) path_expression
1183: .get(2));
1184: }
1185: }
1186: }
1187:
1188: /**
1189: * Visit the specified relative path expression.
1190: *
1191: * @param rp_expression The relative path expression node.
1192: * @return The value of the relative path expression.
1193: */
1194: public Sequence<?> visitRelativePathExpression(
1195: GNode rp_expression) {
1196: // it's just a step expression
1197: if (1 == rp_expression.size()) {
1198: return (Sequence<?>) dispatch((GNode) rp_expression
1199: .get(0));
1200: } else {
1201: // evaluate the outer focus
1202: Sequence<?> outer_focus = (Sequence<?>) dispatch((GNode) rp_expression
1203: .get(0));
1204: environment.pushFocus(outer_focus);
1205:
1206: // set the focus modifier
1207: String focus_modifier = (String) rp_expression.get(1);
1208: if ("/".equals(focus_modifier)) {
1209: focus_flag = FOCUS_LAST;
1210: } else { // it's "//"
1211: focus_flag = FOCUS_ALL;
1212: }
1213: Sequence<?> inner_focus = (Sequence<?>) dispatch((GNode) rp_expression
1214: .get(2));
1215: // pop the outer focus
1216: environment.popFocus();
1217: return inner_focus;
1218: }
1219: }
1220:
1221: /**
1222: * Visit the specified step expression.
1223: *
1224: * @param step_expression The step expression node.
1225: * @return The value of the step expression.
1226: */
1227: public Sequence<?> visitStepExpression(GNode step_expression) {
1228: // get the step expression's item test
1229: GNode test = step_expression.getGeneric(0);
1230: // set aside space for predicates
1231: GNode predicates = null;
1232:
1233: // if there are predicates, capture them
1234: if (2 == step_expression.size()) {
1235: predicates = step_expression.getGeneric(1);
1236: }
1237:
1238: // collect the tree items that satisfy the test
1239: Sequence<?> result = collect(test);
1240:
1241: // set the result
1242: if (null == predicates) {
1243: return result;
1244: } else {
1245: // store the intermediate result as the implicit focus
1246: environment.pushFocus(result);
1247: // dispatch the predicate list
1248: result = (Sequence) dispatch(predicates);
1249: // remove the intermediate result from the focus stack
1250: environment.popFocus();
1251: return result;
1252: }
1253: }
1254:
1255: /**
1256: * Visit the specified predicate list.
1257: *
1258: * @param predicates The list of predicates.
1259: * @return The current outer focus filtered by the predicate list.
1260: */
1261: public Sequence<Item> visitPredicateList(GNode predicates) {
1262: // this list stores the filtered tree items
1263: Sequence<Item> filtered = castToSequenceOfItem(environment
1264: .peekFocus());
1265:
1266: // filter the items on each predicate
1267: for (Iterator<Object> predicate_iterator = predicates
1268: .iterator(); predicate_iterator.hasNext();) {
1269:
1270: // evaluate the predicate for the current focus
1271: filtered = intersection(
1272: filtered,
1273: castToSequenceOfItem(dispatch((GNode) predicate_iterator
1274: .next())));
1275: if (filtered.isEmpty()) {
1276: // No items satisfied the filter
1277: break;
1278: } else {
1279: // replace the current focus with the filtered result
1280: environment.popFocus();
1281: environment.pushFocus(filtered);
1282: }
1283: }
1284: return filtered;
1285: }
1286:
1287: /**
1288: * Visit the specified predicate.
1289: *
1290: * @param predicate The predicate.
1291: * @return The current outer focus filtered by the predicate.
1292: */
1293: public Sequence<?> visitPredicate(GNode predicate) {
1294: Object value_object = dispatch((GNode) predicate.get(0));
1295:
1296: //crude, fix me
1297: if (value_object instanceof Sequence
1298: && !((Sequence<?>) value_object).isEmpty()
1299: && ((Sequence<?>) value_object).get(0) instanceof Integer)
1300: value_object = ((Sequence) value_object).get(0);
1301:
1302: // if it's an integer, we'll want to grab the focus item at that index
1303: if (value_object instanceof Integer) {
1304: int index = ((Integer) value_object).intValue();
1305: Sequence<Item> outer_focus = castToSequenceOfItem(environment
1306: .peekFocus());
1307:
1308: if ((1 <= index) && (index <= outer_focus.size())) {
1309: // wrap the item in its own list
1310: Sequence<Item> item_wrapper = new Sequence<Item>();
1311: item_wrapper.add(outer_focus.get(index - 1));
1312: return item_wrapper;
1313: } else {
1314: return new Sequence<Item>();
1315: }
1316: } else { // otherwise, return the filtered outer focus
1317: return (Sequence<?>) value_object;
1318: }
1319: }
1320:
1321: /**
1322: * Collect items in the target AST that satisfy the criteria of
1323: * an item test.
1324: * @param test_node The test node
1325: * @return The items that satisfy an item test
1326: */
1327: private Sequence<?> collect(GNode test_node) {
1328: // the type of item test
1329: String test_name = test_node.getName();
1330:
1331: // gather the outer focus nodes
1332: Sequence<Item> outer_focus = null;
1333:
1334: // Here, we need to set up the focus
1335: // notice how variable references, parenthesized expressions and
1336: // function calls can be used as a focus, but Identifiers and string
1337: // literals can't (they NEED some kind of parent).
1338: if ((focus_flag == FOCUS_ROOT) || (focus_flag == FOCUS_ALL)) {
1339: // set the initial focus to be the root node
1340: outer_focus = new Sequence<Item>();
1341: outer_focus.add(item_tree);
1342: } else if (focus_flag == FOCUS_INSIDE_OUT) {
1343: // we can just use the previously compiled one
1344: if (!bad_breadth_flag) {
1345: outer_focus = castToSequenceOfItem(bfs_sequence);
1346: } else {
1347: bfs_sequence = reverse_bft(item_tree);
1348: outer_focus = castToSequenceOfItem(bfs_sequence);
1349: bad_breadth_flag = false;
1350: }
1351: } else if ((FOCUS_IMPLICIT == focus_flag)
1352: && (!"ContextItem".equals(test_name))) {
1353:
1354: Sequence<Object> t_val = null;
1355: if ("VariableReference".equals(test_name)) {
1356: t_val = castToSequenceOfObject(environment
1357: .getVariable((String) test_node.get(0)));
1358: if (null == t_val) {
1359: String msg = "Error, Line "
1360: + test_node.getLocation().line
1361: + ": Variable "
1362: + (String) test_node.get(0)
1363: + " not initialized.";
1364: throw new RuntimeException(msg);
1365: } else {
1366: return t_val;
1367: }
1368: } else if ("ParenthesizedExpression".equals(test_name)) {
1369: return (Sequence) dispatch(test_node);
1370: } else if ("FunctionCall".equals(test_name)) {
1371: t_val = new Sequence<Object>();
1372: Object o = dispatch(test_node);
1373: if (o instanceof Integer) {
1374: t_val.add(o);
1375: } else {
1376: t_val.addAll((List<?>) o);
1377: }
1378: return t_val;
1379: } else if ("Identifier".equals(test_name)) {
1380:
1381: String item_name = (String) test_node.get(0);
1382: Sequence<?> foo = environment.peekFocus();
1383: Sequence<?> maybeParents = environment.popFocus();
1384: environment.pushFocus(foo);
1385: t_val = new Sequence<Object>();
1386:
1387: for (Iterator<?> parent_iterator = maybeParents
1388: .flatIterator(); parent_iterator.hasNext();) {
1389: Item parent = (Item) parent_iterator.next();
1390: List<Item> l = parent.getChildren();
1391:
1392: for (int i = 0; i < l.size(); i++) {
1393: Item item = l.get(i);
1394: Object o = item.object;
1395: if (o instanceof GNode) {
1396: String tmp = ((GNode) o).getName();
1397: if (tmp.equals(item_name)) {
1398: t_val.add(parent);
1399: }
1400: }
1401: }
1402: }
1403: return t_val;
1404: }
1405:
1406: } else { // continuing focus
1407: try {
1408: outer_focus = castToSequenceOfItem(environment
1409: .peekFocus());
1410: } catch (NoSuchElementException nse) {
1411: String msg = "Error, Line "
1412: + test_node.getLocation().line
1413: + ": Attempted to evaluate a path expression without focus.";
1414: throw new RuntimeException(msg);
1415: }
1416: }
1417: Sequence<Item> value = new Sequence<Item>();
1418:
1419: // we want to consider every element of the focus -
1420: // first we take care of primary expressions that work on the outer
1421: // focus, then we try to match up its children
1422: if (FOCUS_ALL == focus_flag) {
1423: return test(test_node, outer_focus);
1424: } else if ("ContextItem".equals(test_name)) {
1425: return outer_focus;
1426: } else if ("FunctionCall".equals(test_name)) {
1427: return (Sequence) dispatch(test_node);
1428: } else if ("ReverseStep" == test_name) {
1429: Sequence<Item> parents = new Sequence<Item>();
1430: for (Iterator<?> parent_iterator = outer_focus
1431: .flatIterator(); parent_iterator.hasNext();) {
1432:
1433: Item parent = ((Item) parent_iterator.next()).parent;
1434:
1435: if (null == parent) {
1436: String msg = "Error, Line "
1437: + test_node.getLocation().line
1438: + ": Item has no parent.";
1439: throw new RuntimeException(msg);
1440: } else {
1441: parents.add(parent);
1442: }
1443: }
1444: value.addAll(parents);
1445: } else {
1446: // collect all of the children
1447: Sequence<Item> child_items = new Sequence<Item>();
1448:
1449: for (Iterator<?> parent_iterator = outer_focus
1450: .flatIterator(); parent_iterator.hasNext();) {
1451:
1452: Item parent_item = (Item) parent_iterator.next();
1453: Item child_item;
1454:
1455: if ((null != parent_item.object)
1456: && (parent_item.object instanceof GNode)
1457: && (null != parent_item.children)) {
1458:
1459: for (Iterator<?> child_iterator = parent_item.children
1460: .iterator(); child_iterator.hasNext();) {
1461:
1462: child_item = (Item) child_iterator.next();
1463: child_items = castToSequenceOfItem(child_item
1464: .addToList(castToListOfObject(child_items)));
1465: }
1466: }
1467: }
1468: value = union(value, test(test_node, child_items));
1469: }
1470: return value;
1471: }
1472:
1473: /**
1474: * Determine if items pass the step-expression test.
1475: * @param test_node The item to test
1476: * @param items
1477: * @return The value of the step-expression
1478: */
1479: private Sequence<Item> test(GNode test_node,
1480: Sequence<Item> items) {
1481: Sequence<Item> value = new Sequence<Item>();
1482:
1483: String test_name = test_node.getName();
1484: Iterator<?> item_iterator = null;
1485:
1486: // we'll consider each type of primary expression in turn
1487: if ("ReverseStep".equals(test_name)) {
1488: // If the primary Expression is a "..", we'll want to add the
1489: // parent of item to the result sequence
1490: for (item_iterator = items.flatIterator(); item_iterator
1491: .hasNext();) {
1492: Item parent = ((Item) item_iterator.next()).parent;
1493: if (null == parent) {
1494: String msg = "Error, Line "
1495: + test_node.getLocation().line
1496: + ": Item has no parent.";
1497: throw new RuntimeException(msg);
1498: } else {
1499: value = castToSequenceOfItem(parent
1500: .addToList(castToListOfObject(value)));
1501: }
1502: }
1503: } else if ("Wildcard".equals(test_name)) {
1504: // If the primary expression is a wildcard, we'll simply add
1505: // item to the result sequence
1506: // I also realize that I'm discarding the memory I allocated above
1507: value = items;
1508: } else if ("ContextItem".equals(test_name)) {
1509: // was addAll
1510: value = items;
1511: } else if ("Identifier".equals(test_name)) {
1512:
1513: // if item is a GNode, see if its name matches the identifier
1514: for (item_iterator = items.flatIterator(); item_iterator
1515: .hasNext();) {
1516: Item item = (Item) item_iterator.next();
1517: if ((null != item.object)
1518: && (item.object instanceof GNode)) {
1519: String item_name = ((GNode) item.object)
1520: .getName();
1521:
1522: if (item_name.equals(test_node.get(0))) {
1523: value = castToSequenceOfItem(item
1524: .addToList(castToListOfObject(value)));
1525: }
1526: }
1527: }
1528: } else if ("StringLiteral".equals(test_name)) {
1529: String s = (String) test_node.get(0);
1530: s = s.substring(1, s.length() - 1);
1531:
1532: for (item_iterator = items.flatIterator(); item_iterator
1533: .hasNext();) {
1534: Item item = (Item) item_iterator.next();
1535: // if the item is a string, see if it matches the string literal
1536: if ((null != item.object)
1537: && (item.object instanceof String)) {
1538: if (s.equals(item.object)) {
1539: value = castToSequenceOfItem(item
1540: .addToList(castToListOfObject(value)));
1541: }
1542: }
1543: }
1544:
1545: } else if ("FunctionCall".equals(test_name)) {
1546: environment.pushFocus(items);
1547: value = castToSequenceOfItem(dispatch(test_node));
1548: environment.popFocus();
1549: } else {
1550: // it's either a VariableReference or a parenthesized single
1551: // expression
1552: Sequence<Item> child_value = null;
1553: if ("VariableReference".equals(test_name)) {
1554: // get the variable's value
1555: Sequence<Item> var_val = castToSequenceOfItem(environment
1556: .getVariable((String) test_node.get(0)));
1557: if (null == var_val) {
1558: String msg = "Error, Line "
1559: + test_node.getLocation().line
1560: + ": Variable "
1561: + (String) test_node.get(0)
1562: + " not initialized.";
1563: throw new RuntimeException(msg);
1564: } else {
1565: child_value = var_val;
1566: }
1567: } else { // evaluate the parenthesized single expression
1568: child_value = castToSequenceOfItem(dispatch(test_node));
1569: }
1570: // only add sequence elements that are elements of children
1571: value = intersection(items, child_value);
1572: }
1573:
1574: // if we're searching every node, we'll want to recurse into the
1575: // children of element
1576: if (FOCUS_ALL == focus_flag) {
1577:
1578: Sequence<Item> child_items = new Sequence<Item>();
1579: for (item_iterator = items.flatIterator(); item_iterator
1580: .hasNext();) {
1581: Item parent_item = (Item) item_iterator.next();
1582:
1583: if ((null != parent_item.object)
1584: && (parent_item.object instanceof GNode)
1585: && (null != parent_item.children)) {
1586:
1587: for (Iterator<Item> child_iterator = parent_item.children
1588: .iterator(); child_iterator.hasNext();) {
1589:
1590: child_items.add(child_iterator.next());
1591: }
1592: }
1593: }
1594: if (!child_items.isEmpty()) {
1595: value = union(value, test(test_node, child_items));
1596: }
1597:
1598: }
1599:
1600: return value;
1601: }
1602:
1603: /**
1604: * Visit the specified parenthesized-expression.
1605: *
1606: * @param pe The parenthesized expression node.
1607: * @return The value of the expression.
1608: */
1609: public Sequence<Item> visitParenthesizedExpression(GNode pe) {
1610: int old_focus_flag = focus_flag;
1611: Sequence<Item> value = castToSequenceOfItem(dispatch((GNode) pe
1612: .get(0)));
1613: focus_flag = old_focus_flag;
1614:
1615: // want to account for empty sequence creation
1616: return value == null ? new Sequence<Item>() : value;
1617: }
1618:
1619: /**
1620: * Visit the specified integer-literal node.
1621: *
1622: * @param integer_literal The integer-literal node.
1623: * @return The decimal value of the integer literal.
1624: */
1625: public Integer visitIntegerLiteral(GNode integer_literal) {
1626: return new Integer(Integer.parseInt(
1627: (String) integer_literal.get(0), 10));
1628: }
1629:
1630: /**
1631: * Visit the specified identifier node.
1632: *
1633: * @param id The identifier node.
1634: * @return The value of the identifier node.
1635: */
1636: public String visitIdentifier(GNode id) {
1637: return (String) id.get(0);
1638: }
1639:
1640: /**
1641: * Visit the specified function call call node.
1642: *
1643: * @param function_call The function call node.
1644: * @return The value of the function call.
1645: */
1646: public Object visitFunctionCall(GNode function_call) {
1647: String function_name = (String) dispatch((GNode) function_call
1648: .get(0));
1649: GNode arg_node = (GNode) function_call.get(1);
1650: ArrayList<Object> arg_list = null;
1651:
1652: if (null != arg_node) {
1653: ArrayList<Object> temp = new ArrayList<Object>();
1654: temp.addAll((List<?>) dispatch((GNode) function_call
1655: .get(1)));
1656: arg_list = temp;
1657: }
1658:
1659: try {
1660: return callFunction(function_name, arg_list);
1661: } catch (IllegalArgumentException iae) {
1662: String msg = "Error, Line "
1663: + function_call.getLocation().line
1664: + ": External function " + function_name
1665: + " not found.";
1666: throw new IllegalArgumentException(msg);
1667: }
1668:
1669: }
1670:
1671: /**
1672: * Visit the specified argument list.
1673: *
1674: * @param args The argument list node.
1675: * @return The arguments.
1676: */
1677: public ArrayList<Object> visitArgumentList(GNode args) {
1678: int nchildren = args.size();
1679: ArrayList<Object> arg_list = new ArrayList<Object>(
1680: nchildren);
1681:
1682: for (Iterator<Object> arg_iterator = args.iterator(); arg_iterator
1683: .hasNext();) {
1684:
1685: arg_list.add(dispatch((GNode) arg_iterator.next()));
1686: }
1687:
1688: return arg_list;
1689: }
1690:
1691: /**
1692: * Visit the specified intersection expression.
1693: *
1694: * @param expression The expression.
1695: * @return The intersection of two sequences.
1696: */
1697: public Sequence<Item> visitIntersectionExpression(
1698: GNode expression) {
1699: Sequence<Item> a = castToSequenceOfItem(dispatch((GNode) expression
1700: .get(0)));
1701: Sequence<Item> b = castToSequenceOfItem(dispatch((GNode) expression
1702: .get(1)));
1703:
1704: return intersection(a, b);
1705: }
1706:
1707: /**
1708: * Visit the specified union expression.
1709: *
1710: * @param expression The expression.
1711: * @return The union of two sequences.
1712: */
1713: public Sequence<Item> visitUnionExpression(GNode expression) {
1714: Sequence<Item> a = castToSequenceOfItem(dispatch((GNode) expression
1715: .get(0)));
1716: Sequence<Item> b = castToSequenceOfItem(dispatch((GNode) expression
1717: .get(1)));
1718: return union(a, b);
1719: }
1720:
1721: /**
1722: * Visit the specified differ expression.
1723: *
1724: * @param expression The differ expression node.
1725: * @return The difference of two sequences.
1726: */
1727: public Sequence<Item> visitDifferExpression(GNode expression) {
1728: Sequence<Item> a = castToSequenceOfItem(dispatch((GNode) expression
1729: .get(0)));
1730: Sequence<Item> b = castToSequenceOfItem(dispatch((GNode) expression
1731: .get(1)));
1732: return difference(a, b);
1733: }
1734:
1735: /**
1736: * Visit the specified "or" expression.
1737: *
1738: * @param expression The expression.
1739: * @return The value of the "or" expression.
1740: */
1741: public Sequence<Item> visitOrExpression(GNode expression) {
1742: Sequence<Item> value = null;
1743:
1744: for (Iterator<Object> exp_iterator = expression.iterator(); exp_iterator
1745: .hasNext();) {
1746:
1747: value = castToSequenceOfItem(dispatch((GNode) exp_iterator
1748: .next()));
1749: if (!value.isEmpty()) {
1750: return value;
1751: } else {
1752: continue;
1753: }
1754: }
1755:
1756: // should only return null if the expression doesn't have any children,
1757: // which shouldn't conceivably happen.
1758: return value;
1759: }
1760:
1761: /**
1762: * Visit the specified "and" expression.
1763: *
1764: * @param expression The expression.
1765: * @return The value of the "and" expression.
1766: */
1767: public Sequence<Object> visitAndExpression(GNode expression) {
1768: Sequence<Object> value = null, result = new Sequence<Object>();
1769:
1770: for (Iterator<Object> exp_iterator = expression.iterator(); exp_iterator
1771: .hasNext();) {
1772:
1773: value = castToSequenceOfObject(dispatch((GNode) exp_iterator
1774: .next()));
1775:
1776: if (value.isEmpty()) {
1777: return value;
1778: } else {
1779: result.addAll(value);
1780: }
1781: }
1782: return result;
1783: }
1784:
1785: /**
1786: * Determine the logical union of two sequences.
1787: * @param a The first sequence
1788: * @param b The second sequence
1789: * @return the value of the union expression
1790: */
1791: private Sequence<Item> union(Sequence<Item> a, Sequence<Item> b) {
1792: Sequence<Item> union_list = new Sequence<Item>();
1793: if (null != a) {
1794: union_list.addAll(a);
1795: }
1796:
1797: if (null != b) {
1798: for (Iterator<?> b_iterator = b.flatIterator(); b_iterator
1799: .hasNext();) {
1800: Item b_item = (Item) b_iterator.next();
1801: union_list = castToSequenceOfItem(b_item
1802: .addToList(castToListOfObject(union_list)));
1803: }
1804: }
1805: return union_list;
1806: }
1807:
1808: /**
1809: * Determine the logical intersection of two sequences.
1810: * @param a The first sequence
1811: * @param b The second sequence
1812: * @return The value of the intersection expression
1813: */
1814: private Sequence<Item> intersection(Sequence<Item> a,
1815: Sequence<Item> b) {
1816: Sequence<Item> intersection_list = new Sequence<Item>();
1817:
1818: if ((null != a) && (null != b)) {
1819: for (Iterator<?> a_iterator = a.flatIterator(); a_iterator
1820: .hasNext();) {
1821: Object a_object = a_iterator.next();
1822: if (b.contains(a_object)) {
1823: intersection_list.add((Item) a_object);
1824: }
1825: }
1826: }
1827:
1828: return intersection_list;
1829: }
1830:
1831: /**
1832: * Determine the logical difference between the specified
1833: * sequences.
1834: *
1835: * @param a The first sequence.
1836: * @param b The second sequence.
1837: * @return The logical difference.
1838: */
1839: private Sequence<Item> difference(Sequence<Item> a,
1840: Sequence<Item> b) {
1841: Sequence<Item> diffList = a;
1842:
1843: if ((null != a) && (null != b)) {
1844: for (Iterator<?> bIter = b.flatIterator(); bIter
1845: .hasNext();) {
1846: Object b_object = bIter.next();
1847: if (b.contains(b_object)) {
1848: diffList.remove(b_object);
1849: }
1850: }
1851: }
1852: return diffList;
1853: }
1854:
1855: /**
1856: * Flip the AST upside-down, and then flatten into a sequence using a
1857: * breadth-first traversal.
1858: * @param parent_item
1859: * @return The sequence representing the upside down ast
1860: */
1861: private Sequence<Item> reverse_bft(Item parent_item) {
1862: Sequence<Item> parents = new Sequence<Item>();
1863: Sequence<Item> rev_tree = new Sequence<Item>();
1864:
1865: Item pi = parent_item;
1866:
1867: parents.add(pi);
1868:
1869: while (!parents.isEmpty()) {
1870: pi = parents.removeFirst();
1871:
1872: if (parent_item.object instanceof GNode) {
1873: if (null != pi.children) {
1874: for (Iterator<Item> i = pi.children.iterator(); i
1875: .hasNext();) {
1876: Item child_item = i.next();
1877: parents.addFirst(child_item);
1878: }
1879: }
1880: }
1881: rev_tree.addFirst(pi);
1882: }
1883: return rev_tree;
1884: }
1885: } // end class QueryVisitor
1886:
1887: /** MagiCast (TM). Cast to list of sequence*/
1888: @SuppressWarnings("unchecked")
1889: <T> List<Sequence<?>> castToListOfSequence(T o) {
1890: return (List<Sequence<?>>) o;
1891: }
1892:
1893: /** MagiCast (TM). Cast to list of objects*/
1894: @SuppressWarnings("unchecked")
1895: <T> List<Object> castToListOfObject(T o) {
1896: return (List<Object>) o;
1897: }
1898:
1899: /** MagiCast (TM). Cast to sequence of item*/
1900: @SuppressWarnings("unchecked")
1901: <T> Sequence<Item> castToSequenceOfItem(T o) {
1902: return (Sequence<Item>) o;
1903: }
1904:
1905: /** MagiCast (TM). Cast to sequence of object*/
1906: @SuppressWarnings("unchecked")
1907: <T> Sequence<Object> castToSequenceOfObject(T o) {
1908: return (Sequence<Object>) o;
1909: }
1910:
1911: } // end class Engine
|