001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2007 New York University
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public License
007: * version 2.1 as published by the Free Software Foundation.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the Free Software
016: * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
017: * USA.
018: */
019: package xtc.typical;
020:
021: import xtc.util.Pair;
022: import xtc.util.Runtime;
023:
024: import xtc.tree.Node;
025:
026: import java.util.ArrayList;
027:
028: /**
029: * A Typical Reduction
030: *
031: * @author Laune Harris
032: * @version $Revision: 1.22 $
033: */
034: @SuppressWarnings("unchecked")
035: public class Reduction {
036:
037: /** The runtime */
038: protected Runtime runtime;
039:
040: /** The location node */
041: protected Node location;
042:
043: /** The target list */
044: protected Pair<Node> target;
045:
046: /** The set of patterns. */
047: protected ArrayList<Analyzer.NodeMatch[]> patterns;
048:
049: /** The set of results. */
050: protected ArrayList<Object> results;
051:
052: /** The resulting matches */
053: protected Pair<Object> matches = Pair.empty();
054:
055: /** This flag indicates that the reduction has a 'singleton' constraint */
056: protected boolean sing = false;
057:
058: /** This flag indicates that the reduction has a 'required' constraint */
059: protected boolean req = false;
060:
061: /** This flag indicates that the reduction has a 'duplicate' constraint */
062: protected boolean dup = false;
063:
064: /** This flag indicates that the reduction has a 'noduplicate' constraint */
065: protected boolean nodup = false;
066:
067: /** This flag indicates that the reduction has a 'set' constraint */
068: protected boolean set = false;
069:
070: /** This flag indicates that the reduction has a 'optional' constraint */
071: protected boolean opt = false;
072:
073: /** This flag indicates that the reduction has a 'list' constraint */
074: protected boolean list = false;
075:
076: /** Flag indicating that we've seen an error*/
077: protected boolean error = false;
078:
079: /** This is the string value used for error reporting */
080: protected String tag;
081:
082: /**
083: * Create a new reduction
084: */
085: public Reduction(Pair<Node> target, Runtime runtime, Node location) {
086: patterns = new ArrayList<Analyzer.NodeMatch[]>();
087: results = new ArrayList<Object>();
088: this .target = target;
089: this .location = location;
090: this .runtime = runtime;
091:
092: //by default don't allow duplicates
093: nodup = true;
094: }
095:
096: /**
097: * add a pattern to this
098: */
099: public void addPattern(Object result, Analyzer.NodeMatch... pattern) {
100: results.add(result);
101: patterns.add(pattern);
102: }
103:
104: /**
105: * set opt to true
106: */
107: public void setOpt() {
108: opt = true;
109: }
110:
111: /**
112: * set list to true
113: */
114: public void setList() {
115: list = true;
116: }
117:
118: /**
119: * set list to true
120: */
121: public void setSet() {
122: set = true;
123: }
124:
125: /**
126: * set list to true
127: */
128: public void setSing() {
129: sing = true;
130: }
131:
132: /**
133: * set list to true
134: */
135: public void setReq() {
136: req = true;
137: }
138:
139: /**
140: * set list to true
141: */
142: public void setNodup() {
143: nodup = true;
144: }
145:
146: /**
147: * set list to true
148: */
149: public void setDup() {
150: dup = true;
151: }
152:
153: /**
154: * set the tag
155: * @param tag the tag to set
156: */
157: public void setTag(String tag) {
158: this .tag = tag;
159: }
160:
161: /**
162: * Apply the reduction.
163: *
164: * @return The given result value if the reduction is sucessful,
165: * null otherwise
166: */
167: public Object apply() {
168: /* Here's what should be goin on. We've got a list of arrays of patterns
169: * We iterate from the longest array of patterns to the shortets and apply
170: * each array on the list. If there's a successful match we tag all the
171: * matches nodes with 'used = yes' to remove them from the available pool.
172: * we also record the position of the pattern that matched. At the end
173: * we check the constraints against the result and report an error message
174: * if necessary. This is probably not the most efficient way to do this
175: * right now, but it seems to be correct.
176: */
177: ArrayList<Integer> positions = new ArrayList<Integer>();
178:
179: //TODO sort the patterns from longest to shortest
180:
181: boolean dupError = false;
182:
183: for (Node n : target) {
184: n.setProperty("used", "no");
185: }
186:
187: //iterate over the patterns from longest to shortest
188: for (int i = 0; i < patterns.size(); i++) {
189:
190: //this flag indicates that all sub patterns in a pattern array match
191: //the list
192: boolean allMatch = true;
193: int matchCount = 0;
194:
195: //apply the pattern to the list
196: for (Analyzer.NodeMatch nodeMatch : patterns.get(i)) {
197: boolean match = isMatch(nodeMatch);
198: if (match)
199: matchCount++;
200: allMatch = allMatch && match;
201: }
202:
203: //if matched tag all the matching nodes with 'used=yes'
204: if (allMatch && (matchCount == patterns.get(i).length)) {
205: positions.add(i);
206: for (Node n : target) {
207: if ("maybe".equals(n.getProperty("used"))) {
208: n.setProperty("used", "yes");
209: }
210: }
211:
212: if (nodup) {
213: //check for duplicates
214: //do it all over again if there's another match we give an error
215: allMatch = true;
216: matchCount = 0;
217:
218: //apply the pattern to the list
219: for (Analyzer.NodeMatch nodeMatch : patterns.get(i)) {
220: boolean match = isMatch(nodeMatch);
221: if (match)
222: matchCount++;
223: allMatch = allMatch && match;
224: }
225:
226: if (allMatch
227: && (matchCount == patterns.get(i).length)) {
228: dupError = true;
229: }
230: }
231:
232: } else {
233: //otherwise tag them with 'used=no'
234: for (Node n : target) {
235: if ("maybe".equals(n.getProperty("used"))) {
236: n.setProperty("used", "no");
237: }
238: }
239: }
240: }
241:
242: int size = positions.size();
243:
244: if (dupError) {
245: runtime.error("duplicate " + tag + "s defined");
246: return null;
247: }
248:
249: //constraint and error checks
250: if (sing && size > 1) {
251: runtime.error("multiple " + tag + "s defined", location);
252: return null;
253: }
254:
255: if (req && size == 0) {
256: runtime.error("required " + tag, location);
257: return null;
258: }
259:
260: if (list) {
261: Pair<Object> values = Pair.EMPTY;
262: for (int i : positions) {
263: values = new Pair<Object>(results.get(i), values);
264: }
265:
266: return values.reverse();
267: }
268:
269: if (positions.size() > 0) {
270: return results.get(positions.get(0));
271: }
272:
273: return null;
274: }
275:
276: /**
277: * @return <code>true</code> if this pattern matches a node in the list
278: * <code>false</code> otherwise.
279: */
280: private boolean isMatch(Analyzer.NodeMatch nm) {
281: for (Node n : target) {
282: if ("no".equals(n.getProperty("used")) && nm.apply(n)) {
283: n.setProperty("used", "maybe");
284: return true;
285: }
286: }
287: return false;
288: }
289:
290: /**
291: * Return the node that matches a given pattern. This is useful for
292: * as pattern.
293: *
294: * @return the matching node
295: */
296: public Node getMatch(Analyzer.NodeMatch nm) {
297: for (Object n : target) {
298: if (nm.apply((Node) n))
299: return (Node) n;
300: }
301: return null;
302: }
303:
304: }
|