001: /* ====================================================================
002: * Tea - Copyright (c) 1997-2000 Walt Disney Internet Group
003: * ====================================================================
004: * The Tea Software License, Version 1.1
005: *
006: * Copyright (c) 2000 Walt Disney Internet Group. All rights reserved.
007: *
008: * Redistribution and use in source and binary forms, with or without
009: * modification, are permitted provided that the following conditions
010: * are met:
011: *
012: * 1. Redistributions of source code must retain the above copyright
013: * notice, this list of conditions and the following disclaimer.
014: *
015: * 2. Redistributions in binary form must reproduce the above copyright
016: * notice, this list of conditions and the following disclaimer in
017: * the documentation and/or other materials provided with the
018: * distribution.
019: *
020: * 3. The end-user documentation included with the redistribution,
021: * if any, must include the following acknowledgment:
022: * "This product includes software developed by the
023: * Walt Disney Internet Group (http://opensource.go.com/)."
024: * Alternately, this acknowledgment may appear in the software itself,
025: * if and wherever such third-party acknowledgments normally appear.
026: *
027: * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must
028: * not be used to endorse or promote products derived from this
029: * software without prior written permission. For written
030: * permission, please contact opensource@dig.com.
031: *
032: * 5. Products derived from this software may not be called "Tea",
033: * "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet",
034: * "Kettle", "Trove" or "BeanDoc" appear in their name, without prior
035: * written permission of the Walt Disney Internet Group.
036: *
037: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
038: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
039: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
040: * DISCLAIMED. IN NO EVENT SHALL THE WALT DISNEY INTERNET GROUP OR ITS
041: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
042: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
043: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
044: * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
045: * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
046: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
047: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
048: * ====================================================================
049: *
050: * For more information about Tea, please see http://opensource.go.com/.
051: */
052:
053: package com.go.tea.compiler;
054:
055: import java.util.Collection;
056: import java.util.ArrayList;
057: import java.util.Map;
058: import java.util.HashMap;
059: import java.util.Set;
060: import java.util.HashSet;
061: import java.util.Iterator;
062: import com.go.tea.parsetree.Variable;
063: import com.go.tea.parsetree.VariableRef;
064: import com.go.tea.parsetree.TypeName;
065:
066: /******************************************************************************
067: * A Scope encapsulates a set of declared variables and references to them.
068: * Scopes can be nested, and child scopes have access to variables in the
069: * parent scope.
070: *
071: * @author Brian S O'Neill
072: * @version
073: * <!--$$Revision:--> 28 <!-- $-->, <!--$$JustDate:--> 00/11/16 <!-- $-->
074: */
075: public class Scope {
076: // Shared variables, maps Variable objects to Variable objects.
077: private Map mVariables;
078: private Scope mParent;
079: private Collection mChildren;
080:
081: // Set of private Variables declared in this scope.
082: private Set mPrivateVars;
083:
084: // Maps String variable names to Variable objects for locally available
085: // variables.
086: private Map mDeclared = new HashMap(11);
087:
088: // Contains a list of all the VariableRefs used in this scope.
089: private Collection mVariableRefs = new ArrayList();
090:
091: public Scope() {
092: this (null);
093: }
094:
095: public Scope(Scope parent) {
096: if ((mParent = parent) != null) {
097: mVariables = parent.mVariables;
098: if (parent.mChildren == null) {
099: parent.mChildren = new ArrayList(5);
100: }
101: parent.mChildren.add(this );
102: } else {
103: mVariables = new HashMap(53);
104: }
105: }
106:
107: /**
108: * Returns null if this scope has no parent.
109: */
110: public Scope getParent() {
111: return mParent;
112: }
113:
114: /**
115: * Returns an empty array if this scope has no children.
116: */
117: public Scope[] getChildren() {
118: if (mChildren == null) {
119: return new Scope[0];
120: } else {
121: return (Scope[]) mChildren.toArray(new Scope[mChildren
122: .size()]);
123: }
124: }
125:
126: /**
127: * Declare a variable for use in this scope. If no variable of this name
128: * and type has been defined, it is added to the shared set of pooled
129: * variables. Returns the actual Variable object that should be used.
130: */
131: public Variable declareVariable(Variable var) {
132: return declareVariable(var, false);
133: }
134:
135: /**
136: * Declare a variable for use in this scope. If no variable of this name
137: * and type has been defined, it is added to the shared set of pooled
138: * variables. Returns the actual Variable object that should be used
139: * instead.
140: *
141: * @param isPrivate when true, variable declaration doesn't leave this
142: * scope during an intersection or promotion
143: */
144: public Variable declareVariable(Variable var, boolean isPrivate) {
145: if (mVariables.containsKey(var)) {
146: var = (Variable) mVariables.get(var);
147: } else {
148: mVariables.put(var, var);
149: }
150:
151: mDeclared.put(var.getName(), var);
152:
153: if (isPrivate) {
154: if (mPrivateVars == null) {
155: mPrivateVars = new HashSet(7);
156: }
157: mPrivateVars.add(var);
158: } else {
159: if (mPrivateVars != null) {
160: mPrivateVars.remove(var);
161: }
162: }
163:
164: return var;
165: }
166:
167: /**
168: * Declare new variables in this scope. Entries in the array are replaced
169: * with actual Variable objects that should be used instead.
170: */
171: public void declareVariables(Variable[] vars) {
172: for (int i = 0; i < vars.length; i++) {
173: vars[i] = declareVariable(vars[i]);
174: }
175: }
176:
177: /**
178: * Returns a declared variable by name. Search begins in this scope and
179: * moves up into parent scopes. If not found, null is returned. The
180: * returned variable may be private or public to a scope.
181: *
182: * @return Null if no declared variable found with the given name
183: */
184: public Variable getDeclaredVariable(String name) {
185: return getDeclaredVariable(name, false);
186: }
187:
188: /**
189: * Returns a declared variable by name. Search begins in this scope and
190: * moves up into parent scopes. If not found, null is returned. A public-
191: * only variable can be requested.
192: *
193: * @return Null if no declared variable found with the given name
194: */
195: public Variable getDeclaredVariable(String name, boolean publicOnly) {
196: //private Set mPrivateVars;
197:
198: Variable var = (Variable) mDeclared.get(name);
199: if (var != null) {
200: // If its okay to be private or its public then...
201: if (!publicOnly || mPrivateVars == null
202: || !mPrivateVars.contains(var)) {
203: return var;
204: }
205: }
206:
207: if (mParent != null) {
208: return mParent.getDeclaredVariable(name);
209: }
210:
211: return null;
212: }
213:
214: /**
215: * Returns all the variables declared in this scope.
216: *
217: * @return non-null array of locally declared variables
218: */
219: private Variable[] getLocallyDeclaredVariables() {
220: Collection vars = mDeclared.values();
221: return (Variable[]) vars.toArray(new Variable[vars.size()]);
222: }
223:
224: /**
225: * Attempt to bind variable reference to a variable in this scope or a
226: * parent scope. If the variable to bind to isn't available or doesn't
227: * exist, false is returned.
228: *
229: * @return true if reference has been bound
230: */
231: public boolean bindToVariable(VariableRef ref) {
232: String name = ref.getName();
233: Variable var = getDeclaredVariable(name);
234:
235: if (var != null) {
236: ref.setType(null);
237: ref.setVariable(var);
238: mVariableRefs.add(ref);
239: return true;
240: } else {
241: return false;
242: }
243: }
244:
245: /**
246: * Returns all the variable references made from this scope and all child
247: * scopes.
248: *
249: * @return non-null array of VariableRefs.
250: */
251: public VariableRef[] getVariableRefs() {
252: Collection allRefs = new ArrayList();
253: fillVariableRefs(allRefs, this );
254: return (VariableRef[]) allRefs.toArray(new VariableRef[allRefs
255: .size()]);
256: }
257:
258: private static void fillVariableRefs(Collection refs, Scope scope) {
259: refs.addAll(scope.mVariableRefs);
260:
261: Collection children = scope.mChildren;
262: if (children != null) {
263: Iterator it = children.iterator();
264: while (it.hasNext()) {
265: fillVariableRefs(refs, (Scope) it.next());
266: }
267: }
268: }
269:
270: /**
271: * Returns all the references made from this scope to variables declared
272: * in this scope or in a parent.
273: *
274: * @return non-null array of VariableRefs.
275: */
276: public VariableRef[] getLocalVariableRefs() {
277: VariableRef[] refs = new VariableRef[mVariableRefs.size()];
278: return (VariableRef[]) mVariableRefs.toArray(refs);
279: }
280:
281: /**
282: * Returns all the references made from this scope and all child scopes to
283: * variables declared outside of this scope.
284: */
285: public VariableRef[] getOutOfScopeVariableRefs() {
286: Scope parent;
287: if ((parent = getParent()) == null) {
288: return new VariableRef[0];
289: }
290:
291: Collection allRefs = new ArrayList();
292: fillVariableRefs(allRefs, this );
293:
294: Collection refs = new ArrayList(allRefs.size());
295:
296: Iterator it = allRefs.iterator();
297: while (it.hasNext()) {
298: VariableRef ref = (VariableRef) it.next();
299: Variable var = ref.getVariable();
300: if (var != null
301: && parent.getDeclaredVariable(var.getName()) == var) {
302: refs.add(ref);
303: }
304: }
305:
306: VariableRef[] refsArray = new VariableRef[refs.size()];
307: return (VariableRef[]) refs.toArray(refsArray);
308: }
309:
310: /**
311: * Returns all the references made from this scope to variables declared
312: * outside of this scope.
313: */
314: public VariableRef[] getLocalOutOfScopeVariableRefs() {
315: Scope parent;
316: if ((parent = getParent()) == null) {
317: return new VariableRef[0];
318: }
319:
320: Collection refs = new ArrayList(mVariableRefs.size());
321:
322: Iterator it = mVariableRefs.iterator();
323: while (it.hasNext()) {
324: VariableRef ref = (VariableRef) it.next();
325: Variable var = ref.getVariable();
326: if (var != null
327: && parent.getDeclaredVariable(var.getName()) == var) {
328: refs.add(ref);
329: }
330: }
331:
332: VariableRef[] refsArray = new VariableRef[refs.size()];
333: return (VariableRef[]) refs.toArray(refsArray);
334: }
335:
336: /**
337: * Returns true if this scope is the same as or a parent of the one given.
338: */
339: public boolean isEnclosing(Scope scope) {
340: for (; scope != null; scope = scope.getParent()) {
341: if (this == scope) {
342: return true;
343: }
344: }
345: return false;
346: }
347:
348: /**
349: * Returns the innermost enclosing scope of this and the one given. If no
350: * enclosing scope exists, null is returned.
351: */
352: public Scope getEnclosingScope(Scope scope) {
353: for (Scope s = this ; s != null; s = s.getParent()) {
354: if (s.isEnclosing(scope)) {
355: return s;
356: }
357: }
358: return null;
359: }
360:
361: /**
362: * Returns the intersection of this scope against the one given. An
363: * intersection operates on each scope's locally declared variables,
364: * producing a list of variables that both scopes may inherit.
365: * <p>
366: * The list may contain undeclared variables, and so all returned variables
367: * must be re-declared in a common parent scope. This responsibility is
368: * left to the caller, intersect does not alter the internal state of
369: * either scope.
370: * <p>
371: * This method is designed specifically for combining the locally
372: * declared variables of the "then" and "else" parts of an if statement.
373: *
374: * @return variables representing the intersection
375: */
376: public Variable[] intersect(Scope scope) {
377: Collection intersection = new ArrayList();
378:
379: // A set of variable names that have been moved into the intersection.
380: Set matchedNames = new HashSet(7);
381:
382: intersectFrom(this , scope, matchedNames, intersection);
383: intersectFrom(scope, this , matchedNames, intersection);
384:
385: Variable[] vars = new Variable[intersection.size()];
386: return (Variable[]) intersection.toArray(vars);
387: }
388:
389: /**
390: * Returns variables to promote from this scope to a parent scope.
391: * Promote is similar to intersect, except it operates on this scope and
392: * its parent (if it has one).
393: * <p>
394: * The list may contain undeclared variables, and so all returned variables
395: * must be re-declared in a common parent scope. This responsibility is
396: * left to the caller, promote does not alter the internal state of this
397: * scope or its parent.
398: * <p>
399: * This method is designed specifically for promoting the locally
400: * declared variables of a loop statement's body.
401: *
402: * @return variables to promote
403: */
404: public Variable[] promote() {
405: Scope parent = getParent();
406: if (parent == null) {
407: return new Variable[0];
408: }
409:
410: Collection promotion = new ArrayList();
411:
412: // A set of variable names that have been moved into the promotion.
413: Set matchedNames = new HashSet(7);
414:
415: intersectFrom(this , parent, matchedNames, promotion);
416:
417: Variable[] vars = new Variable[promotion.size()];
418: return (Variable[]) promotion.toArray(vars);
419: }
420:
421: private static void intersectFrom(Scope scope1, Scope scope2,
422: Set matchedNames, Collection vars) {
423: Set privates1 = scope1.mPrivateVars;
424:
425: Variable[] vars1 = scope1.getLocallyDeclaredVariables();
426: for (int i = 0; i < vars1.length; i++) {
427: Variable var1 = vars1[i];
428: if (privates1 != null && privates1.contains(var1)) {
429: continue;
430: }
431:
432: String varName = var1.getName();
433:
434: if (matchedNames.contains(varName)) {
435: // This variable has already been moved into the intersection.
436: continue;
437: } else {
438: matchedNames.add(varName);
439: }
440:
441: Variable var2 = scope2.getDeclaredVariable(varName, true);
442:
443: if (var2 == null) {
444: // No matching public variable in scope2, so continue.
445: continue;
446: }
447:
448: Type type1 = var1.getType();
449: Type type2 = var2.getType();
450:
451: // Find common type.
452: Type type = type1.getCompatibleType(type2);
453: if (type == null) {
454: continue;
455: }
456: Class clazz = type.getNaturalClass();
457:
458: // Find a variable to hold common type.
459: Variable var;
460: if (type.equals(type1)) {
461: var = var1;
462: } else if (type.equals(type2)) {
463: var = var2;
464: } else {
465: // Create a new variable with the common type.
466: var = new Variable(var1.getSourceInfo(), varName, type);
467: }
468:
469: vars.add(var);
470: }
471: }
472:
473: /**
474: * Delete this scope by detaching it from its parent.
475: */
476: public void delete() {
477: Scope parent = getParent();
478: if (parent != null) {
479: parent.mChildren.remove(this );
480: }
481: }
482:
483: public String toString() {
484: StringBuffer buf = new StringBuffer();
485: buf.append(super .toString());
486: buf.append('\n');
487: append(buf, this , "");
488: return buf.toString();
489: }
490:
491: private void append(StringBuffer buf, Scope scope, String indent) {
492: buf.append(indent);
493: buf.append("{\n");
494:
495: String indentMore = indent + " ";
496:
497: Variable[] vars = scope.getLocallyDeclaredVariables();
498: for (int i = 0; i < vars.length; i++) {
499: Variable var = vars[i];
500:
501: buf.append(indentMore);
502:
503: Set privateVars = scope.mPrivateVars;
504: if (privateVars != null && privateVars.contains(var)) {
505: buf.append("private ");
506: }
507:
508: Type type = var.getType();
509: if (type != null) {
510: buf.append(type.getFullName());
511: } else {
512: buf.append("<null>");
513: }
514:
515: buf.append(' ');
516: buf.append(var.getName());
517:
518: buf.append("; // ");
519: buf.append(var);
520: buf.append('\n');
521: }
522:
523: VariableRef[] refs = scope.getLocalVariableRefs();
524: for (int i = 0; i < refs.length; i++) {
525: VariableRef ref = refs[i];
526:
527: buf.append(indentMore);
528: buf.append(ref.getName());
529:
530: buf.append("; // ");
531: buf.append(ref);
532: buf.append(" to ");
533: buf.append(ref.getVariable());
534: buf.append('\n');
535: }
536:
537: Scope[] children = scope.getChildren();
538: for (int i = 0; i < children.length; i++) {
539: append(buf, children[i], indentMore);
540: }
541:
542: buf.append(indent);
543: buf.append("}\n");
544: }
545: }
|