0001: /*
0002: * xtc - The eXTensible Compiler
0003: * Copyright (C) 2007 Robert Grimm
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: package xtc.type;
0020:
0021: import java.util.ArrayList;
0022: import java.util.Collections;
0023: import java.util.HashMap;
0024: import java.util.HashSet;
0025: import java.util.Iterator;
0026: import java.util.List;
0027: import java.util.Map;
0028: import java.util.Set;
0029:
0030: import xtc.Constants;
0031: import xtc.Constants.FuzzyBoolean;
0032:
0033: import xtc.tree.Printer;
0034:
0035: import xtc.util.Utilities;
0036:
0037: /**
0038: * Common type operations for <em>Rats!</em> ASTs.
0039: *
0040: * <p />This class supports two views on a grammar's generic AST. The
0041: * first view is dynamically typed, with all generic AST nodes
0042: * represented by the canonical node type. The second view is
0043: * statically typed, with all generic AST nodes represented by tuples
0044: * organized into variants. Either way, this class supports the
0045: * following types:<ul>
0046: *
0047: * <li>The void type represented by {@link VoidT}.</li>
0048: *
0049: * <li>The unit type represented by {@link UnitT}.</li>
0050: *
0051: * <li>Characters represented by an {@link InternalT} with name
0052: * "char".</li>
0053: *
0054: * <li>Strings represented by an {@link InternalT} with name
0055: * "string".</li>
0056: *
0057: * <li>Tokens represented by an {@link InternalT} with name
0058: * "token".</li>
0059: *
0060: * <li>Dynamically typed nodes represented by an {@link InternalT}
0061: * with name "node".</li>
0062: *
0063: * <li>Statically typed nodes represented by a {@link VariantT} with
0064: * {@link TupleT} elements.</li>
0065: *
0066: * <li>Parse tree annotations represented by an {@link InternalT}
0067: * with name "formatting".</li>
0068: *
0069: * <li>Lists represented by an {@link InternalT} with name
0070: * "list".</li>
0071: *
0072: * <li>Actions represented by an {@link InternalT} with name
0073: * "action".</li>
0074: *
0075: * </ul>
0076: *
0077: * All node types have the {@link Constants#ATT_NODE} attribute; the
0078: * dynamically typed node representing generic productions also has
0079: * the {@link Constants#ATT_GENERIC} attribute.
0080: *
0081: * <p />In addition to generic ASTs, this class also supports
0082: * user-defined types, which must be represented by types that are not
0083: * listed above.
0084: *
0085: * <p />Concrete subclasses specify the mapping between strings and
0086: * types. For mapping internal representations back to strings, the
0087: * void type has name "void", the unit type has name "unit", and the
0088: * wildcard has name "?".
0089: *
0090: * @author Robert Grimm
0091: * @version $Revision: 1.36 $
0092: */
0093: public abstract class AST {
0094:
0095: /** The set of internal type names. */
0096: public static final Set<String> INTERNAL;
0097:
0098: /** The canonical void type, which is {@link VoidT#TYPE}. */
0099: public static final Type VOID = VoidT.TYPE;
0100:
0101: /** The canonical any type. */
0102: public static final Type ANY;
0103:
0104: /** The canonical character reference type. */
0105: public static final Type CHAR;
0106:
0107: /** The canonical string type. */
0108: public static final Type STRING;
0109:
0110: /** The canonical token type. */
0111: public static final Type TOKEN;
0112:
0113: /** The canonical dynamically typed node type. */
0114: public static final Type NODE;
0115:
0116: /** The canonical null node type. */
0117: public static final Type NULL_NODE;
0118:
0119: /** The canonical dynamically typed generic node type. */
0120: public static final Type GENERIC;
0121:
0122: /** The canonical formatting node type. */
0123: public static final Type FORMATTING;
0124:
0125: /** The canonical parameterized list type. */
0126: public static final Type LIST;
0127:
0128: /** The canonical list instantiated with a wildcard element type. */
0129: public static final Type WILD_LIST;
0130:
0131: /** The canonical parameterized action type. */
0132: public static final Type ACTION;
0133:
0134: /** The canonical action instantiated with a wildcard element type. */
0135: public static final Type WILD_ACTION;
0136:
0137: static {
0138: // Create the set of internal type names.
0139: Set<String> internal = new HashSet<String>();
0140:
0141: internal.add("any");
0142: internal.add("char");
0143: internal.add("string");
0144: internal.add("token");
0145: internal.add("node");
0146: internal.add("formatting");
0147: internal.add("list");
0148: internal.add("action");
0149:
0150: INTERNAL = Collections.unmodifiableSet(internal);
0151:
0152: // Create the canonical types.
0153: ANY = new InternalT("any");
0154: CHAR = new InternalT("char");
0155: STRING = new InternalT("string");
0156: TOKEN = new InternalT("token");
0157: TOKEN.addAttribute(Constants.ATT_NODE);
0158: NODE = new InternalT("node");
0159: NODE.addAttribute(Constants.ATT_NODE);
0160: NULL_NODE = new UnitT();
0161: NULL_NODE.addAttribute(Constants.ATT_NODE);
0162: GENERIC = new InternalT("node");
0163: GENERIC.addAttribute(Constants.ATT_NODE);
0164: GENERIC.addAttribute(Constants.ATT_GENERIC);
0165: FORMATTING = new InternalT("formatting");
0166: FORMATTING.addAttribute(Constants.ATT_NODE);
0167: LIST = new ParameterizedT(new Parameter("element"),
0168: new InternalT("list"));
0169: WILD_LIST = new InstantiatedT(Wildcard.TYPE, LIST);
0170: ACTION = new ParameterizedT(new Parameter("element"),
0171: new InternalT("action"));
0172: WILD_ACTION = new InstantiatedT(Wildcard.TYPE, ACTION);
0173:
0174: // Seal the canincal types.
0175: ANY.seal();
0176: CHAR.seal();
0177: STRING.seal();
0178: TOKEN.seal();
0179: NULL_NODE.seal();
0180: NODE.seal();
0181: GENERIC.seal();
0182: FORMATTING.seal();
0183: LIST.seal();
0184: WILD_LIST.seal();
0185: ACTION.seal();
0186: WILD_ACTION.seal();
0187: }
0188:
0189: // ==========================================================================
0190:
0191: /** The map from strings to type representations. */
0192: protected final Map<String, Type> externToIntern;
0193:
0194: /**
0195: * The map from internal type names to external types. Valid type
0196: * names are void, unit, any, char, string, token, node, formatting,
0197: * list, and action as well as ? for wildcards.
0198: */
0199: protected final Map<String, String> internToExtern;
0200:
0201: /**
0202: * The list of imported module names. Each module name should end
0203: * with the separator necessary for creating a fully qualified type
0204: * name by appending a simple name.
0205: */
0206: protected final List<String> importedModules;
0207:
0208: /** The map from simple type names to fully qualified type names. */
0209: protected final Map<String, String> importedTypes;
0210:
0211: /** The map from variant names to variant types. */
0212: protected final Map<String, VariantT> variants;
0213:
0214: /** The map from variant names to nodes. */
0215: protected final Map<String, Set<String>> variantNodes;
0216:
0217: /** The map from unqualified variant names to original names. */
0218: protected final Map<String, String> originalNames;
0219:
0220: /** The map from tuple names to tuple types. */
0221: protected final Map<String, TupleT> tuples;
0222:
0223: /** The map from tuple names to variants containing the tuples. */
0224: protected final Map<String, List<VariantT>> tupleVariants;
0225:
0226: /**
0227: * Create a new instance. This constructor allocates the internal
0228: * data structures for mapping between external and internal types
0229: * but does not initialize them.
0230: *
0231: * @see #initialize(boolean,boolean,boolean,boolean)
0232: */
0233: public AST() {
0234: externToIntern = new HashMap<String, Type>();
0235: internToExtern = new HashMap<String, String>();
0236: importedModules = new ArrayList<String>();
0237: importedTypes = new HashMap<String, String>();
0238: variants = new HashMap<String, VariantT>();
0239: variantNodes = new HashMap<String, Set<String>>();
0240: originalNames = new HashMap<String, String>();
0241: tuples = new HashMap<String, TupleT>();
0242: tupleVariants = new HashMap<String, List<VariantT>>();
0243: }
0244:
0245: /**
0246: * Initialize the mapping between external and internal
0247: * representations. This method fills the {@link #externToIntern}
0248: * and {@link #internToExtern} data structures.
0249: *
0250: * @param hasNode Flag to indicate use of built-in nodes.
0251: * @param hasToken Flag to indicate use of tokens.
0252: * @param hasFormatting Flag to indicate use of formatting.
0253: * @param hasAction Flag to indicate use of actions.
0254: */
0255: public abstract void initialize(boolean hasNode, boolean hasToken,
0256: boolean hasFormatting, boolean hasAction);
0257:
0258: // ==========================================================================
0259:
0260: /**
0261: * Import the specified module. This method adds the module to the
0262: * list of imported modules {@link #importedModules}. The specified
0263: * module name must end with the appropriate separator.
0264: *
0265: * @param module The module name.
0266: */
0267: public void importModule(String module) {
0268: if (!importedModules.contains(module)) {
0269: importedModules.add(module);
0270: }
0271: }
0272:
0273: /**
0274: * Import the specified type. This method adds a mapping from the
0275: * specified simple type name to the specified qualified type name
0276: * to the imported types {@link #importedTypes}.
0277: *
0278: * @param qualified The fully qualified name.
0279: * @param simple The simple name.
0280: */
0281: public void importType(String qualified, String simple) {
0282: if (importedTypes.containsKey(simple)) {
0283: assert qualified.equals(importedTypes.get(simple));
0284: } else {
0285: importedTypes.put(simple, qualified);
0286: }
0287: }
0288:
0289: // ==========================================================================
0290:
0291: /**
0292: * Determine whether the specified string represents the void type.
0293: *
0294: * @param s The type as a string.
0295: * @return <code>true</code> if the string represents the void type.
0296: */
0297: public abstract boolean isVoid(String s);
0298:
0299: /**
0300: * Determine whether the specified string represents the generic
0301: * node type.
0302: *
0303: * @param s The type as a string.
0304: * @return <code>true</code> if the string represents the generic
0305: * node type.
0306: */
0307: public abstract boolean isGenericNode(String s);
0308:
0309: // ==========================================================================
0310:
0311: /**
0312: * Convert the specified string representation of a type into the
0313: * type. This method defers to {@link #internList(String)}, {@link
0314: * #internAction(String)}, and {@link #internUser(String)} for list,
0315: * action, and user-defined types, respectively.
0316: *
0317: * @param s The type as a string.
0318: * @return The type.
0319: */
0320: public Type intern(String s) {
0321: // Try the map from strings to types.
0322: Type type = externToIntern.get(s);
0323: if (null != type)
0324: return type;
0325:
0326: // Try as a list.
0327: type = internList(s);
0328: if (!type.isError())
0329: return type;
0330:
0331: // Try as an action.
0332: type = internAction(s);
0333: if (!type.isError())
0334: return type;
0335:
0336: // Treat as user-defined.
0337: return internUser(s);
0338: }
0339:
0340: /**
0341: * Convert the specified string representation of a list type into
0342: * the type.
0343: *
0344: * @param s The list type as a string.
0345: * @return The type or {@link ErrorT#TYPE} if the string does not
0346: * represent a list.
0347: */
0348: protected abstract Type internList(String s);
0349:
0350: /**
0351: * Convert the specified string representation of an action type
0352: * into the type.
0353: *
0354: * @param s The action type as a string.
0355: * @return The type or {@link ErrorT#TYPE} if the string does not
0356: * represent an action.
0357: */
0358: protected abstract Type internAction(String s);
0359:
0360: /**
0361: * Convert the specified string representation of a user-defined
0362: * type into its internal representation.
0363: *
0364: * @param s The user-defined type as a string.
0365: * @return The type.
0366: */
0367: protected abstract Type internUser(String s);
0368:
0369: // ==========================================================================
0370:
0371: /**
0372: * Convert the specified type to a string. This method defers to
0373: * {@link #externList(Type)}, {@link #externAction(Type)}, and
0374: * {@link #externUser(Type)} for list, action, and user-defined
0375: * types, respectively.
0376: *
0377: * @param type The type.
0378: * @return The type as a string.
0379: */
0380: public String extern(Type type) {
0381: String s;
0382:
0383: switch (type.tag()) {
0384: case VARIANT:
0385: case TUPLE:
0386: if (type.hasAttribute(Constants.ATT_NODE)) {
0387: return internToExtern.get("node");
0388: } else {
0389: return externUser(type);
0390: }
0391:
0392: case INTERNAL: {
0393: String name = type.resolve().toInternal().getName();
0394:
0395: if ("list".equals(name)) {
0396: return externList(type);
0397: } else if ("action".equals(name)) {
0398: return externAction(type);
0399: } else if (INTERNAL.contains(name)) {
0400: return internToExtern.get(name);
0401: } else {
0402: return externUser(type);
0403: }
0404: }
0405:
0406: case UNIT:
0407: return type.hasAttribute(Constants.ATT_NODE) ? internToExtern
0408: .get("node")
0409: : internToExtern.get("unit");
0410:
0411: case VOID:
0412: return internToExtern.get("void");
0413:
0414: case WILDCARD:
0415: return internToExtern.get(type.resolve().toWildcard()
0416: .getName());
0417:
0418: case ERROR:
0419: throw new AssertionError("Error type");
0420:
0421: default:
0422: return externUser(type);
0423: }
0424: }
0425:
0426: /**
0427: * Convert the specified list type to a string.
0428: *
0429: * @param type The list type.
0430: * @return The type as a string.
0431: */
0432: protected abstract String externList(Type type);
0433:
0434: /**
0435: * Convert the specified action type to a string.
0436: *
0437: * @param type The action type.
0438: * @return The type as a string.
0439: */
0440: protected abstract String externAction(Type type);
0441:
0442: /**
0443: * Convert the specified user-defined type to a string.
0444: *
0445: * @param type The user-defined type.
0446: * @return The type as a string.
0447: */
0448: protected abstract String externUser(Type type);
0449:
0450: // ==========================================================================
0451:
0452: /**
0453: * Determine whether instances of the specified type have a source
0454: * location. This method defers to {@link #hasLocationUser(Type)}
0455: * for user-defined types.
0456: *
0457: * @param type The type.
0458: * @return The inexact answer.
0459: */
0460: public FuzzyBoolean hasLocation(Type type) {
0461: switch (type.tag()) {
0462: case VARIANT:
0463: case TUPLE:
0464: if (type.hasAttribute(Constants.ATT_NODE)) {
0465: return FuzzyBoolean.TRUE;
0466: } else {
0467: return hasLocationUser(type);
0468: }
0469:
0470: case INTERNAL:
0471: if (type.hasAttribute(Constants.ATT_NODE)) {
0472: return FuzzyBoolean.TRUE;
0473: } else {
0474: String name = type.resolve().toInternal().getName();
0475:
0476: if ("any".equals(name)) {
0477: return FuzzyBoolean.MAYBE;
0478: } else if (INTERNAL.contains(name)) {
0479: return FuzzyBoolean.FALSE;
0480: } else {
0481: return hasLocationUser(type);
0482: }
0483: }
0484:
0485: case UNIT:
0486: return type.hasAttribute(Constants.ATT_NODE) ? FuzzyBoolean.TRUE
0487: : FuzzyBoolean.FALSE;
0488:
0489: case VOID:
0490: return FuzzyBoolean.FALSE;
0491:
0492: case PARAMETER:
0493: case WILDCARD:
0494: return FuzzyBoolean.MAYBE;
0495:
0496: case ERROR:
0497: throw new AssertionError("Error type");
0498:
0499: default:
0500: return hasLocationUser(type);
0501: }
0502: }
0503:
0504: /**
0505: * Determine whether instances of the specified user-defined type
0506: * have a source location.
0507: *
0508: * @param type The type.
0509: * @return The inexact answer.
0510: */
0511: protected abstract FuzzyBoolean hasLocationUser(Type type);
0512:
0513: // ==========================================================================
0514:
0515: /**
0516: * Determine whether the specified type is optional.
0517: *
0518: * @param type The type.
0519: * @return <code>true</code> if the specified type is optional.
0520: */
0521: public static boolean isOptional(Type type) {
0522: return type.hasAttribute(Constants.ATT_OPTIONAL);
0523: }
0524:
0525: /**
0526: * Determine whether the specified type is variable.
0527: *
0528: * @param type The type.
0529: * @return <code>true</code> if the specified type is variable.
0530: */
0531: public static boolean isVariable(Type type) {
0532: return type.hasAttribute(Constants.ATT_VARIABLE);
0533: }
0534:
0535: // ==========================================================================
0536:
0537: /**
0538: * Determine whether the specified type is the void type.
0539: *
0540: * @param type The type.
0541: * @return <code>true</code> if the type is the void type.
0542: */
0543: public static boolean isVoid(Type type) {
0544: return type.resolve().isVoid();
0545: }
0546:
0547: /**
0548: * Determine whether the specified type is the any type.
0549: *
0550: * @param type The type.
0551: * @return <code>true</code> if the type is the any type.
0552: */
0553: public static boolean isAny(Type type) {
0554: Type r = type.resolve();
0555: return r.isInternal() && "any".equals(r.toInternal().getName());
0556: }
0557:
0558: /**
0559: * Determine whether the specified type is a character.
0560: *
0561: * @param type The type.
0562: * @return <code>true</code> if the type is a character.
0563: */
0564: public static boolean isChar(Type type) {
0565: Type r = type.resolve();
0566: return r.isInternal()
0567: && "char".equals(r.toInternal().getName());
0568: }
0569:
0570: /**
0571: * Determine whether the specified type is a string.
0572: *
0573: * @param type The type.
0574: * @return <code>true</code> if the type is a string.
0575: */
0576: public static boolean isString(Type type) {
0577: Type r = type.resolve();
0578: return r.isInternal()
0579: && "string".equals(r.toInternal().getName());
0580: }
0581:
0582: /**
0583: * Determine whether the specified type is a token.
0584: *
0585: * @param type The type.
0586: * @return <code>true</code> if the type is a token.
0587: */
0588: public static boolean isToken(Type type) {
0589: Type r = type.resolve();
0590: return r.isInternal()
0591: && "token".equals(r.toInternal().getName());
0592: }
0593:
0594: /**
0595: * Determine whether the specified type is a node.
0596: *
0597: * @param type The type.
0598: * @return <code>true</code> if the type is a node.
0599: */
0600: public static boolean isNode(Type type) {
0601: return type.hasAttribute(Constants.ATT_NODE);
0602: }
0603:
0604: /**
0605: * Determine whether the specified type is a dynamically typed node.
0606: *
0607: * @param type The type.
0608: * @return <code>true</code> if the type is a dynamically typed
0609: * node.
0610: */
0611: public static boolean isDynamicNode(Type type) {
0612: Type r = type.resolve();
0613: return r.isInternal()
0614: && "node".equals(r.toInternal().getName());
0615: }
0616:
0617: /**
0618: * Determine whether the specified type is a null node.
0619: *
0620: * @param type The type.
0621: * @return <code>true</code> if the type is a null node.
0622: */
0623: public static boolean isNullNode(Type type) {
0624: return type.hasAttribute(Constants.ATT_NODE)
0625: && type.resolve().isUnit();
0626: }
0627:
0628: /**
0629: * Determine whether the specified type is a statically typed node.
0630: *
0631: * @param type The type.
0632: * @return <code>true</code> if the type is a statically typed node.
0633: */
0634: public static boolean isStaticNode(Type type) {
0635: return type.hasAttribute(Constants.ATT_NODE)
0636: && type.resolve().isVariant();
0637: }
0638:
0639: /**
0640: * Determine whether the specified type is a generic node.
0641: *
0642: * @param type The type.
0643: * @return <code>true</code> if the type is a generic node.
0644: */
0645: public static boolean isGenericNode(Type type) {
0646: return (type.hasAttribute(Constants.ATT_GENERIC) && type
0647: .hasAttribute(Constants.ATT_NODE));
0648: }
0649:
0650: /**
0651: * Determine whether the specified type is a formatting node.
0652: *
0653: * @param type The type.
0654: * @return <code>true</code> if the type is a formatting node.
0655: */
0656: public static boolean isFormatting(Type type) {
0657: Type r = type.resolve();
0658: return r.isInternal()
0659: && "formatting".equals(r.toInternal().getName());
0660: }
0661:
0662: /**
0663: * Determine whether the specified type is a list.
0664: *
0665: * @param type The type.
0666: * @return <code>true</code> if the type is a list.
0667: */
0668: public static boolean isList(Type type) {
0669: Type r = type.resolve();
0670: return r.isInternal()
0671: && "list".equals(r.toInternal().getName());
0672: }
0673:
0674: /**
0675: * Determine whether the specified type is an action.
0676: *
0677: * @param type The type.
0678: * @return <code>true</code> if the type is an action.
0679: */
0680: public static boolean isAction(Type type) {
0681: Type r = type.resolve();
0682: return r.isInternal()
0683: && "action".equals(r.toInternal().getName());
0684: }
0685:
0686: /**
0687: * Get the specified instantiated type's only argument.
0688: *
0689: * @param type The instantiated type.
0690: * @return The argument type.
0691: */
0692: public static Type getArgument(Type type) {
0693: assert type.hasInstantiated();
0694: assert 1 == type.toInstantiated().getArguments().size();
0695: return type.toInstantiated().getArguments().get(0);
0696: }
0697:
0698: /**
0699: * Determine whether the specified type is user-defined.
0700: *
0701: * @param type The type.
0702: * @return <code>true</code> if the type is a user-defined type.
0703: */
0704: public static boolean isUser(Type type) {
0705: switch (type.tag()) {
0706: case VARIANT:
0707: case TUPLE:
0708: return !type.hasAttribute(Constants.ATT_NODE);
0709:
0710: case INTERNAL:
0711: return !INTERNAL.contains(type.resolve().toInternal()
0712: .getName());
0713:
0714: case UNIT:
0715: case VOID:
0716: case ERROR:
0717: case PARAMETER:
0718: case WILDCARD:
0719: return false;
0720:
0721: default:
0722: return true;
0723: }
0724: }
0725:
0726: // ==========================================================================
0727:
0728: /**
0729: * Mark the specified type as optional.
0730: *
0731: * @param type The type.
0732: * @return The optional type.
0733: */
0734: public static Type markOptional(Type type) {
0735: return type.annotate().attribute(Constants.ATT_OPTIONAL);
0736: }
0737:
0738: /**
0739: * Mark the specified type as variable.
0740: *
0741: * @param type The type.
0742: * @return The variable type.
0743: */
0744: public static Type markVariable(Type type) {
0745: return type.annotate().attribute(Constants.ATT_VARIABLE);
0746: }
0747:
0748: // ==========================================================================
0749:
0750: /**
0751: * Convert the specified production's name into a variant name.
0752: * This method converts the name from <em>Rats!</em>' camel case
0753: * naming convention into ML's lower case with underscores naming
0754: * convention. It preserves any qualifier.
0755: *
0756: * @param name The production's name.
0757: * @return The corresponding variant name.
0758: */
0759: public String toVariantName(String name) {
0760: if (Utilities.isQualified(name)) {
0761: final String qualifier = Utilities.getQualifier(name);
0762: final String unqual = Utilities.getName(name);
0763: return Utilities.qualify(qualifier, Utilities.split(unqual,
0764: '_'));
0765: } else {
0766: return Utilities.split(name, '_');
0767: }
0768: }
0769:
0770: /**
0771: * Determine whether a variant type with the specified name has been
0772: * created before. This method first converts the name from
0773: * <em>Rats!</em>' camel case naming convention into ML's lower case
0774: * with underscores naming convention. It then checks whether a
0775: * variant type with that name has been returned by {@link
0776: * #toVariant(String,boolean)} before.
0777: *
0778: * @see #toVariantName(String)
0779: *
0780: * @param name The name in camel case.
0781: * @return <code>true</code> if a variant type with the name exists.
0782: */
0783: public boolean hasVariant(String name) {
0784: return variants.containsKey(toVariantName(name));
0785: }
0786:
0787: /**
0788: * Get the variant type with the specified name. This method first
0789: * converts the name from <em>Rats!</em>' camel case naming
0790: * convention into ML's lower case with underscores naming
0791: * convention. Then, if this method has not been invoked on the
0792: * specified name before, it returns a new variant type with an
0793: * empty list of tuples. Otherwise, it simply returns the
0794: * previously created variant type. The returned variant type has
0795: * the {@link Constants#ATT_NODE} attribute.
0796: *
0797: * @see #toVariantName(String)
0798: *
0799: * @param name The name in camel case.
0800: * @param poly The flag for whether the variant is polymorphic.
0801: * @return The corresponding variant type.
0802: */
0803: public VariantT toVariant(String name, boolean poly) {
0804: final String vname = toVariantName(name);
0805:
0806: final VariantT variant;
0807: if (variants.containsKey(vname)) {
0808: variant = variants.get(vname);
0809: assert poly == variant.isPolymorphic();
0810: } else {
0811: variant = new VariantT(vname, poly, new ArrayList<TupleT>());
0812: variant.addAttribute(Constants.ATT_NODE);
0813: variants.put(vname, variant);
0814: variantNodes.put(vname, new HashSet<String>());
0815: originalNames.put(vname, name);
0816: }
0817:
0818: return variant;
0819: }
0820:
0821: /**
0822: * Get the original name for the specified variant.
0823: *
0824: * <p />The specified variant must have been created with {@link
0825: * #toVariant(String,boolean)}.
0826: *
0827: * @param variant The variant.
0828: * @return The original name in <em>Rats!</em>' camel case.
0829: */
0830: public String toOriginal(VariantT variant) {
0831: final String vname = variant.getName();
0832:
0833: // Make sure the variant is registered.
0834: assert null != vname;
0835: assert variants.containsKey(vname);
0836: assert variant == variants.get(vname);
0837:
0838: return originalNames.get(vname);
0839: }
0840:
0841: // ==========================================================================
0842:
0843: /**
0844: * Determine whether a tuple type with the specified name has been
0845: * created before.
0846: *
0847: * @param name The name.
0848: * @return <code>true</code> if a tuple type with the name exists.
0849: */
0850: public boolean hasTuple(String name) {
0851: return tuples.containsKey(name);
0852: }
0853:
0854: /**
0855: * Determine whether the tuple type with the specified name has been
0856: * created before and is monomorphic.
0857: *
0858: * @param name The name.
0859: * @return <code>true</code> if a tuple type with the name exists
0860: * and is monomorphic.
0861: */
0862: public boolean isMonomorphic(String name) {
0863: return (tuples.containsKey(name)
0864: && (0 < tupleVariants.get(name).size()) && (!tupleVariants
0865: .get(name).get(0).isPolymorphic()));
0866: }
0867:
0868: /**
0869: * Get the tuple type with the specified name. If this method has
0870: * not been invoked on the specified name before, it returns a new
0871: * tuple type, which is incomplete. Otherwise, it simply returns
0872: * the previoulsy created tuple type.
0873: *
0874: * @param name The name.
0875: * @return The corresponding tuple type.
0876: */
0877: public TupleT toTuple(String name) {
0878: final TupleT tuple;
0879:
0880: if (tuples.containsKey(name)) {
0881: tuple = tuples.get(name);
0882: } else {
0883: tuple = new TupleT(name);
0884: tuples.put(name, tuple);
0885: tupleVariants.put(name, new ArrayList<VariantT>());
0886: }
0887:
0888: return tuple;
0889: }
0890:
0891: /**
0892: * Add the specified tuple type to the specified variant type. If
0893: * the tuple is not a member of the specified variant, this method
0894: * adds it, while also updating its internal state.
0895: *
0896: * <p />The specified tuple must have been created with {@link
0897: * #toTuple(String)} or {@link #toTuple(VariantT)}. The specified
0898: * variant must have been created with {@link
0899: * #toVariant(String,boolean)}.
0900: *
0901: * @param tuple The tuple.
0902: * @param variant The variant.
0903: */
0904: public void add(TupleT tuple, VariantT variant) {
0905: final String tname = tuple.getName();
0906: final String vname = variant.getName();
0907:
0908: // Make sure the tuple is registered.
0909: assert tuples.containsKey(tname);
0910: assert tuple == tuples.get(tname);
0911: assert tupleVariants.containsKey(tname);
0912:
0913: // Make sure the variant is registered.
0914: if (null == vname) {
0915: assert variant.isPolymorphic();
0916: } else {
0917: assert variants.containsKey(vname);
0918: assert variant == variants.get(vname);
0919: }
0920:
0921: // Actually add the tuple.
0922: final Type t = variant.lookup(tname);
0923: if (t.isError()) {
0924: assert variant.isPolymorphic()
0925: || (null != vname && !variantNodes.get(vname)
0926: .contains(tuple.getSimpleName()));
0927:
0928: if (!variant.isPolymorphic()) {
0929: variantNodes.get(vname).add(tuple.getSimpleName());
0930: }
0931: if (null != vname) {
0932: tupleVariants.get(tname).add(variant);
0933: }
0934: variant.getTuples().add(tuple);
0935:
0936: } else {
0937: assert t == tuple;
0938: }
0939: }
0940:
0941: /**
0942: * Get the specified tuple's variants.
0943: *
0944: * <p />The specified tuple must have been created with {@link
0945: * #toTuple(String)} or {@link #toTuple(VariantT)}. It must have
0946: * been added to any variants with {@link #add(TupleT,VariantT)}.
0947: *
0948: * @param tuple The tuple.
0949: * @return The tuple's variants.
0950: */
0951: public List<VariantT> toVariants(TupleT tuple) {
0952: final String tname = tuple.getName();
0953:
0954: // Make sure the tuple is registered.
0955: assert tuples.containsKey(tname);
0956: assert tuple == tuples.get(tname);
0957:
0958: List<VariantT> variants = tupleVariants.get(tname);
0959: assert null != variants;
0960: return variants;
0961: }
0962:
0963: // ==========================================================================
0964:
0965: /**
0966: * Get the polymorphic tuple for the specified variant.
0967: *
0968: * <p />The specified variant must have been created with {@link
0969: * #toVariant(String,boolean)}.
0970: *
0971: * @param variant The variant.
0972: * @return The corresponding polymorphic tuple.
0973: */
0974: public TupleT toTuple(VariantT variant) {
0975: final String vname = variant.getName();
0976:
0977: // Make sure the variant is registered.
0978: assert !variant.isPolymorphic();
0979: assert variants.containsKey(vname);
0980: assert variant == variants.get(vname);
0981:
0982: final String qualifier = variant.getQualifier();
0983:
0984: String tname = "Some"
0985: + Utilities.unqualify(originalNames.get(vname));
0986: if (isMonomorphic(Utilities.qualify(qualifier, tname))) {
0987: tname = "Just" + tname;
0988:
0989: while (isMonomorphic(Utilities.qualify(qualifier, tname))) {
0990: tname = tname + "1";
0991: }
0992: }
0993:
0994: TupleT tuple = toTuple(Utilities.qualify(qualifier, tname));
0995: if (null == tuple.getTypes()) {
0996: tuple.setTypes(new ArrayList<Type>(1));
0997: tuple.getTypes().add(variant);
0998: }
0999:
1000: return tuple;
1001: }
1002:
1003: // ==========================================================================
1004:
1005: /**
1006: * Determine whether the specified variants overlap. Two variants
1007: * overlap if they include tuples representing the same generic
1008: * node.
1009: *
1010: * <p />The specified variants must have been created with {@link
1011: * #toVariant(String,boolean)}.
1012: *
1013: * @param v1 The first variant.
1014: * @param v2 The second variant.
1015: * @return <code>true</code> if the two variants overlap.
1016: */
1017: public boolean overlap(VariantT v1, VariantT v2) {
1018: if (v1.isPolymorphic()) {
1019: for (TupleT tuple : v1.getTuples()) {
1020: if (overlap(tuple.getTypes().get(0).toVariant(), v2))
1021: return true;
1022: }
1023:
1024: } else if (v2.isPolymorphic()) {
1025: for (TupleT tuple : v2.getTuples()) {
1026: if (overlap(v1, tuple.getTypes().get(0).toVariant()))
1027: return true;
1028: }
1029:
1030: } else {
1031: final String vname1 = v1.getName();
1032: final String vname2 = v2.getName();
1033:
1034: assert variants.containsKey(vname1);
1035: assert v1 == variants.get(vname1);
1036: assert variants.containsKey(vname2);
1037: assert v2 == variants.get(vname2);
1038:
1039: final Set<String> nodes1 = variantNodes.get(v1.getName());
1040: final Set<String> nodes2 = variantNodes.get(v2.getName());
1041:
1042: for (String s : nodes1) {
1043: if (nodes2.contains(s))
1044: return true;
1045: }
1046: }
1047:
1048: return false;
1049: }
1050:
1051: // ==========================================================================
1052:
1053: /** The metadata for a grammar's statically typed nodes. */
1054: public static class MetaData {
1055:
1056: /** Create a new metadata record. */
1057: public MetaData() {
1058: reachable = new HashSet<String>();
1059: modularize = false;
1060: }
1061:
1062: /** The names of reachable variants. */
1063: public Set<String> reachable;
1064:
1065: /** The flag for requiring separate modules. */
1066: public boolean modularize;
1067:
1068: }
1069:
1070: /**
1071: * Determine the metadata for the specified variant.
1072: *
1073: * @param variant The variant.
1074: * @return The corresponding metadata.
1075: */
1076: public MetaData getMetaData(VariantT variant) {
1077: MetaData meta = new MetaData();
1078: fillIn(variant, meta, new HashSet<String>());
1079: return meta;
1080: }
1081:
1082: /**
1083: * Fill in the specified metadata for the specified type.
1084: *
1085: * @param type The type.
1086: * @param meta The metadata.
1087: * @param names The simple variant names processed so far.
1088: */
1089: private void fillIn(Type type, MetaData meta, Set<String> names) {
1090: switch (type.tag()) {
1091: case VARIANT: {
1092: final VariantT variant = type.resolve().toVariant();
1093: final String qname = variant.getName();
1094: final String sname = variant.getSimpleName();
1095: final List<TupleT> tuples = variant.getTuples();
1096:
1097: if (null == qname) {
1098: for (TupleT t : tuples)
1099: fillIn(t, meta, names);
1100: } else if (!meta.reachable.contains(qname)) {
1101: meta.reachable.add(qname);
1102: if (names.contains(sname)) {
1103: meta.modularize = true;
1104: } else {
1105: names.add(sname);
1106: }
1107: for (TupleT t : tuples)
1108: fillIn(t, meta, names);
1109: }
1110: }
1111: break;
1112:
1113: case TUPLE: {
1114: final List<Type> types = type.resolve().toTuple()
1115: .getTypes();
1116: if (null != types)
1117: for (Type t : types)
1118: fillIn(t, meta, names);
1119: }
1120: break;
1121:
1122: case INTERNAL: {
1123: final String name = type.resolve().toInternal().getName();
1124:
1125: if ("list".equals(name) || "action".equals(name)) {
1126: if (type.hasInstantiated()) {
1127: fillIn(getArgument(type), meta, names);
1128: }
1129: }
1130: }
1131: break;
1132:
1133: default:
1134: // Nothing to do.
1135: }
1136: }
1137:
1138: // ==========================================================================
1139:
1140: /**
1141: * Create a new list type.
1142: *
1143: * @param element The element type.
1144: * @return The corresponding list type.
1145: */
1146: public static Type listOf(Type element) {
1147: return new InstantiatedT(element, LIST);
1148: }
1149:
1150: /**
1151: * Create a new action type.
1152: *
1153: * @param element The element type.
1154: * @return The corresponding action type.
1155: */
1156: public static Type actionOf(Type element) {
1157: return new InstantiatedT(element, ACTION);
1158: }
1159:
1160: // ==========================================================================
1161:
1162: /**
1163: * Unify the specified types. If the strict flag is set, statically
1164: * and dynamically typed nodes do not unify. If the flag is not
1165: * set, they do unify and otherwise incompatible types unify to the
1166: * any type. This method defers to {@link
1167: * #unify(VariantT,VariantT)} for statically typed nodes and to
1168: * {@link #unifyUser(Type,Type,boolean)} for user-defined types.
1169: *
1170: * @param t1 The first type.
1171: * @param t2 The second type.
1172: * @param strict The flag for strict unification.
1173: * @return The unified type or {@link ErrorT#TYPE} if the two types
1174: * do not unify.
1175: */
1176: public Type unify(Type t1, Type t2, boolean strict) {
1177: // Get the trivial cases out of the way.
1178: if (t1 == t2)
1179: return t1;
1180: if (t1.hasError() || t2.hasError())
1181: return ErrorT.TYPE;
1182: if (t1.resolve().isParameter())
1183: return t2;
1184: if (t2.resolve().isParameter())
1185: return t1;
1186:
1187: // Now, do the real work.
1188: Type result = unify1(t1, t2, strict);
1189:
1190: // Adjust the result for non-strict unification.
1191: if (result.isError() && !strict)
1192: result = ANY;
1193:
1194: // Preserve any variable or optional attribute, in this precedence
1195: // order.
1196: if (!result.isError()) {
1197: if (isVariable(t1) || isVariable(t2)) {
1198: result = markVariable(result);
1199: } else if (isOptional(t1) || isOptional(t2)) {
1200: result = markOptional(result);
1201: }
1202: }
1203:
1204: // Done.
1205: return result;
1206: }
1207:
1208: /**
1209: * Actually unify the specified types.
1210: *
1211: * @param t1 The first type.
1212: * @param t2 The second type.
1213: * @param strict The flag for strict unification.
1214: * @return The unified type or {@link ErrorT#TYPE} if the two types
1215: * do not unify.
1216: */
1217: private Type unify1(Type t1, Type t2, boolean strict) {
1218: Type r1 = t1.resolve(), r2 = t2.resolve();
1219:
1220: if (t1.hasInstantiated() && t2.hasInstantiated()) {
1221: InstantiatedT i1 = t1.toInstantiated(), i2 = t2
1222: .toInstantiated();
1223: List<Type> a1 = i1.getArguments(), a2 = i2.getArguments();
1224:
1225: if (a1.size() != a2.size())
1226: return ErrorT.TYPE;
1227:
1228: Type base = unify(i1.getType(), i2.getType(), true);
1229: if (base.isError())
1230: return ErrorT.TYPE;
1231:
1232: List<Type> args = new ArrayList<Type>(a1.size());
1233: for (int i = 0; i < a1.size(); i++) {
1234: Type t = unify(a1.get(i), a2.get(i), true);
1235: if (t.isError())
1236: return ErrorT.TYPE;
1237: args.add(t);
1238: }
1239:
1240: return new InstantiatedT(args, base);
1241:
1242: } else if (t1.hasInstantiated() || t2.hasInstantiated()) {
1243: return ErrorT.TYPE;
1244:
1245: } else if (isUser(t1) && isUser(t2)) {
1246: return unifyUser(t1, t2, strict);
1247:
1248: } else if (isNode(t1) && isNode(t2)) {
1249: if (isNullNode(t1)) {
1250: return r2;
1251:
1252: } else if (isNullNode(t2)) {
1253: return r1;
1254:
1255: } else if (isToken(t1) && isToken(t2)) {
1256: return TOKEN;
1257:
1258: } else if ((isToken(t1) || isDynamicNode(t1) || isFormatting(t1))
1259: && (isToken(t2) || isDynamicNode(t2) || isFormatting(t2))) {
1260: return NODE;
1261:
1262: } else if (r1.isVariant() && r2.isVariant()) {
1263: return unify(r1.toVariant(), r2.toVariant());
1264:
1265: } else if (strict) {
1266: return ErrorT.TYPE;
1267:
1268: } else {
1269: return NODE;
1270: }
1271:
1272: } else if (r1.isVoid() && r2.isVoid()) {
1273: return VoidT.TYPE;
1274:
1275: } else if (r1.isUnit() && r2.isUnit()) {
1276: return UnitT.TYPE;
1277:
1278: } else if (isChar(t1) && isChar(t2)) {
1279: return CHAR;
1280:
1281: } else if (isString(t1) && isString(t2)) {
1282: return STRING;
1283:
1284: } else if (isList(t1) && isList(t2)) {
1285: return LIST;
1286:
1287: } else if (isAction(t1) && isAction(t2)) {
1288: return ACTION;
1289:
1290: } else {
1291: return ErrorT.TYPE;
1292: }
1293: }
1294:
1295: /**
1296: * Unify the specified statically typed nodes. Statically typed
1297: * nodes unify through polymorphic variant types, unless they
1298: * reference the same underlying AST node.
1299: *
1300: * @param v1 The first variant.
1301: * @param v2 The second variant.
1302: * @return The unified variant.
1303: */
1304: protected Type unify(VariantT v1, VariantT v2) {
1305: // Get the trivial case out of the way.
1306: if ((null != v1.getName()) && v1.getName().equals(v2.getName()))
1307: return v1;
1308:
1309: // Unify the two variants.
1310: List<TupleT> tuples = new ArrayList<TupleT>();
1311: VariantT result = new VariantT(null, true, tuples);
1312: result.addAttribute(Constants.ATT_NODE);
1313:
1314: if (v1.isPolymorphic()) {
1315: tuples.addAll(v1.getTuples());
1316:
1317: if (v2.isPolymorphic()) {
1318: for (TupleT tuple : v2.getTuples()) {
1319: if (!tuples.contains(tuple)) {
1320: final VariantT v3 = tuple.getTypes().get(0)
1321: .toVariant();
1322: if (overlap(v1, v3))
1323: return ErrorT.TYPE;
1324: tuples.add(tuple);
1325: }
1326: }
1327:
1328: } else {
1329: TupleT tuple = toTuple(v2);
1330: if (!tuples.contains(tuple)) {
1331: if (overlap(v1, v2))
1332: return ErrorT.TYPE;
1333: tuples.add(tuple);
1334: }
1335: }
1336:
1337: } else if (v2.isPolymorphic()) {
1338: tuples.addAll(v2.getTuples());
1339:
1340: TupleT tuple = toTuple(v1);
1341: if (!tuples.contains(tuple)) {
1342: if (overlap(v1, v2))
1343: return ErrorT.TYPE;
1344: tuples.add(tuple);
1345: }
1346:
1347: } else {
1348: if (overlap(v1, v2))
1349: return ErrorT.TYPE;
1350: tuples.add(toTuple(v1));
1351: tuples.add(toTuple(v2));
1352: }
1353:
1354: return result;
1355: }
1356:
1357: /**
1358: * Unify the specified user-defined types. Note that this method
1359: * need not handle instantiated types but must preserve parameterize
1360: * types.
1361: *
1362: * @param t1 The first user-defined type.
1363: * @param t2 The second user-defined type.
1364: * @param strict The flag for strict unification.
1365: * @return The unified type or {@link ErrorT#TYPE} if the two types
1366: * do not unify.
1367: */
1368: protected abstract Type unifyUser(Type t1, Type t2, boolean strict);
1369:
1370: // ==========================================================================
1371:
1372: /**
1373: * Flatten the specified tuple type. If the specified tuple has a
1374: * list element, this method combines the first such list type with
1375: * all succeeding element types into a single list type, modifying
1376: * the specified tuple type.
1377: *
1378: * @param tuple The tuple type.
1379: * @param strict The flag for strict unification.
1380: * @return The updated tuple type or {@link ErrorT#TYPE} if types
1381: * cannot be unified.
1382: */
1383: public Type flatten(TupleT tuple, boolean strict) {
1384: final List<Type> types = tuple.getTypes();
1385: final int size = types.size();
1386:
1387: int index = -1; // The index of the first list.
1388: Type element = null; // The element type of the list.
1389: boolean optional = false; // The flag for optional elements.
1390:
1391: for (int i = 0; i < size; i++) {
1392: Type t = types.get(i);
1393:
1394: if (-1 == index) {
1395: if (isList(t)) {
1396: index = i;
1397:
1398: t = getArgument(t);
1399: if (isOptional(t))
1400: optional = true;
1401: t = t.deannotate();
1402:
1403: element = t;
1404: }
1405:
1406: } else {
1407: if (isList(t))
1408: t = getArgument(t);
1409: if (isOptional(t))
1410: optional = true;
1411: t = t.deannotate();
1412:
1413: element = unify(element, t, strict);
1414: if (element.isError())
1415: return ErrorT.TYPE;
1416: }
1417: }
1418:
1419: if (-1 != index) {
1420: // Create the flattened list type.
1421: if (optional)
1422: element = markOptional(element);
1423: Type list = listOf(element);
1424: if (isVariable(types.get(index)))
1425: list = markVariable(list);
1426:
1427: // Update the tuple type.
1428: types.subList(index, size).clear();
1429: types.add(list);
1430: }
1431:
1432: return tuple;
1433: }
1434:
1435: // ==========================================================================
1436:
1437: /**
1438: * Combine the specified tuple types into a consistent type. The
1439: * types must be tuples with the same name.
1440: *
1441: * @param tuple1 The first tuple.
1442: * @param tuple2 The second tuple.
1443: * @param flatten The flag for flattening lists.
1444: * @param strict The flag for strict unification.
1445: * @return The combined tuple type or {@link ErrorT#TYPE} if the two
1446: * tuple types cannot be combined into a consistent type.
1447: */
1448: public Type combine(TupleT tuple1, TupleT tuple2, boolean flatten,
1449: boolean strict) {
1450:
1451: assert tuple1.getName().equals(tuple2.getName());
1452:
1453: // If both tuple types are equal, we are done.
1454: if ((tuple1 == tuple2) || tuple1.equals(tuple2))
1455: return tuple1;
1456:
1457: // Set up.
1458: final List<Type> types1 = tuple1.getTypes(), types2 = tuple2
1459: .getTypes();
1460: final int size1 = types1.size(), size2 = types2.size();
1461:
1462: // If lists are flattened, then find the first list across both
1463: // tuple types and determine the combined list element type.
1464: int listIdx = Integer.MAX_VALUE;
1465: Type elemT = Wildcard.TYPE;
1466: boolean variable = false; // Flag for list being variable.
1467: boolean optional = false; // Flag for element being optional.
1468:
1469: if (flatten) {
1470: // Find the first list type across both tuple types.
1471: for (int i = 0; i < size1; i++) {
1472: Type t = types1.get(i);
1473:
1474: if (isList(t)) {
1475: listIdx = i;
1476: variable = isVariable(t);
1477: break;
1478: }
1479: }
1480:
1481: for (int i = 0; i < size2; i++) {
1482: Type t = types2.get(i);
1483:
1484: if (isList(t)) {
1485: if (i < listIdx) {
1486: listIdx = i;
1487: variable = isVariable(t);
1488: }
1489: break;
1490: }
1491: }
1492:
1493: // Determine the combined list element type.
1494: if (Integer.MAX_VALUE != listIdx) {
1495: for (int i = listIdx; i < size1; i++) {
1496: Type t = types1.get(i);
1497: if (isList(t))
1498: t = getArgument(t);
1499: if (isOptional(t))
1500: optional = true;
1501: t = t.deannotate();
1502:
1503: elemT = unify(elemT, t, strict);
1504: if (elemT.isError())
1505: return ErrorT.TYPE;
1506: }
1507:
1508: for (int i = listIdx; i < size2; i++) {
1509: Type t = types2.get(i);
1510: if (isList(t))
1511: t = getArgument(t);
1512: if (isOptional(t))
1513: optional = true;
1514: t = t.deannotate();
1515:
1516: elemT = unify(elemT, t, strict);
1517: if (elemT.isError())
1518: return ErrorT.TYPE;
1519: }
1520: }
1521: }
1522:
1523: // Determine the combined tuple's element types.
1524: final List<Type> types3 = new ArrayList<Type>(Math.max(size1,
1525: size2));
1526: final int size3 = Math.min(Math.max(size1, size2), listIdx);
1527:
1528: for (int i = 0; i < size3; i++) {
1529: final Type t1 = (i < size1) ? types1.get(i) : null;
1530: final Type t2 = (i < size2) ? types2.get(i) : null;
1531:
1532: Type t3;
1533: if (null == t1) {
1534: t3 = markVariable(t2.deannotate());
1535: } else if (null == t2) {
1536: t3 = markVariable(t1.deannotate());
1537: } else {
1538: t3 = unify(t1.deannotate(), t2.deannotate(), strict);
1539: if (t3.isError())
1540: return ErrorT.TYPE;
1541: if (isVariable(t1) || isVariable(t2)) {
1542: t3 = markVariable(t3);
1543: } else if (isOptional(t1) || isOptional(t2)) {
1544: t3 = markOptional(t3);
1545: } else if ((t1.resolve().isWildcard() || t2.resolve()
1546: .isWildcard())
1547: && !t3.resolve().isWildcard()) {
1548: t3 = markOptional(t3);
1549: }
1550: }
1551:
1552: types3.add(t3);
1553: }
1554:
1555: if (Integer.MAX_VALUE != listIdx) {
1556: if (optional)
1557: elemT = markOptional(elemT);
1558:
1559: Type list = listOf(elemT);
1560: if (variable || (listIdx > size1) || (listIdx > size2)) {
1561: // The new trailing list is variable if (1) the original list
1562: // is variable or (2) the original list is at a position
1563: // beyond one tuple's elements plus one (which accounts for
1564: // the empty list not having any children).
1565: list = markVariable(list);
1566: }
1567:
1568: types3.add(list);
1569: }
1570:
1571: // Done.
1572: return new TupleT(tuple1.getName(), types3);
1573: }
1574:
1575: // ==========================================================================
1576:
1577: /**
1578: * Ensure that the specified type is concrete. This method replaces
1579: * occurrences of the wildcard type with the specified replacement;
1580: * though it does not process variant types to avoid infinite
1581: * recursions. It assumes that list and action types are
1582: * instantiated.
1583: *
1584: * @see #concretizeTuples(VariantT,Type)
1585: *
1586: * @param type The type.
1587: * @param concrete The concrete replacement for wildcards.
1588: * @return The concrete type.
1589: */
1590: public Type concretize(Type type, Type concrete) {
1591: Type resolved = type.resolve(), result = null;
1592:
1593: if (resolved.isWildcard()) {
1594: result = concrete;
1595:
1596: } else if (resolved.isTuple()) {
1597: TupleT tuple = resolved.toTuple();
1598: List<Type> elements = tuple.getTypes();
1599: boolean isCopy = false;
1600:
1601: for (int i = 0; i < elements.size(); i++) {
1602: Type element = concretize(elements.get(i), concrete);
1603:
1604: if (elements.get(i) != element) {
1605: if (!isCopy) {
1606: elements = new ArrayList<Type>(elements);
1607: isCopy = true;
1608: }
1609: elements.set(i, element);
1610: }
1611: }
1612:
1613: if (isCopy)
1614: result = new TupleT(tuple.getName(), elements);
1615:
1616: } else if (isList(type)) {
1617: Type el = concretize(getArgument(type), concrete);
1618: if (el != getArgument(type))
1619: result = listOf(el);
1620:
1621: } else if (isAction(type)) {
1622: Type el = concretize(getArgument(type), concrete);
1623: if (el != getArgument(type))
1624: result = actionOf(el);
1625: }
1626:
1627: if (null == result) {
1628: return type;
1629:
1630: } else {
1631: if (isVariable(type)) {
1632: result = markVariable(result);
1633: } else if (isOptional(type)) {
1634: result = markOptional(result);
1635: }
1636:
1637: return result;
1638: }
1639: }
1640:
1641: /**
1642: * Concretize the specified variant type's tuples. This method
1643: * updates any tuples in place.
1644: *
1645: * @see #concretize(Type,Type)
1646: *
1647: * @param variant The variant.
1648: * @param concrete The concrete replacement for wildcards.
1649: */
1650: public void concretizeTuples(VariantT variant, Type concrete) {
1651: List<TupleT> tuples = variant.getTuples();
1652:
1653: if (null != tuples) {
1654: for (int i = 0; i < tuples.size(); i++) {
1655: tuples.set(i, concretize(tuples.get(i), concrete)
1656: .toTuple());
1657: }
1658: }
1659: }
1660:
1661: // ==========================================================================
1662:
1663: /**
1664: * Print the specified type.
1665: *
1666: * @param printer The printer.
1667: * @param type The type.
1668: * @param refIsDecl The flag for whether a variant type reference
1669: * also is a declaration.
1670: * @param qualified The flag for printing qualified names.
1671: * @param module The current module name, which may be <code>null</code>.
1672: */
1673: public void print(Type type, Printer printer, boolean refIsDecl,
1674: boolean qualified, String module) {
1675: switch (type.tag()) {
1676: case VARIANT: {
1677: final VariantT variant = type.resolve().toVariant();
1678: final boolean poly = variant.isPolymorphic();
1679: final List<TupleT> tuples = variant.getTuples();
1680:
1681: final String name;
1682: if (!qualified
1683: || (null != module && module.equals(variant
1684: .getQualifier()))) {
1685: name = variant.getSimpleName();
1686: } else {
1687: name = variant.getName();
1688: }
1689:
1690: if (null == name) {
1691: printer.pln('[').incr().incr();
1692: for (TupleT tuple : tuples) {
1693: printer.indent().p("| `");
1694: print(tuple, true, printer, qualified, module);
1695: printer.pln();
1696: }
1697: printer.decr().decr().indentMore().p(']');
1698:
1699: } else if (!refIsDecl) {
1700: printer.p(name);
1701:
1702: } else if (poly) {
1703: printer.indent().p("mltype ").p(name).pln(" = [")
1704: .incr();
1705: for (TupleT tuple : tuples) {
1706: printer.indent().p("| `");
1707: print(tuple, true, printer, qualified, module);
1708: printer.pln();
1709: }
1710: printer.decr().indent().pln("];");
1711:
1712: } else if (1 == tuples.size()) {
1713: printer.indent().p("mltype ").p(name).p(" = ");
1714: print(tuples.get(0), false, printer, qualified, module);
1715: printer.pln(" ;");
1716:
1717: } else {
1718: printer.indent().p("mltype ").p(name).pln(" =").incr();
1719: for (Iterator<TupleT> iter = tuples.iterator(); iter
1720: .hasNext();) {
1721: printer.indent().p("| ");
1722: print(iter.next(), false, printer, qualified,
1723: module);
1724: if (iter.hasNext())
1725: printer.pln();
1726: }
1727: printer.pln(" ;").decr();
1728: }
1729: }
1730: break;
1731:
1732: case TUPLE:
1733: print(type.resolve().toTuple(), false, printer, qualified,
1734: module);
1735: break;
1736:
1737: case INTERNAL: {
1738: final String name = type.resolve().toInternal().getName();
1739:
1740: if ("list".equals(name) || "action".equals(name)) {
1741: if (type.hasInstantiated()) {
1742: print(type.toInstantiated().getArguments().get(0),
1743: printer, false, qualified, module);
1744: } else {
1745: print(
1746: type.toParameterized().getParameters().get(
1747: 0), printer, false, qualified,
1748: module);
1749: }
1750: printer.p(' ');
1751: }
1752:
1753: printer.p(name);
1754: }
1755: break;
1756:
1757: case UNIT:
1758: case VOID:
1759: printer.p("bottom");
1760: break;
1761:
1762: case PARAMETER:
1763: case WILDCARD:
1764: printer.p("'").p(type.resolve().toParameter().getName());
1765: break;
1766:
1767: case ERROR:
1768: printer.p("<error>");
1769: break;
1770:
1771: default:
1772: throw new AssertionError("Invalid type " + type);
1773: }
1774:
1775: if (!refIsDecl) {
1776: if (type.hasAttribute(Constants.ATT_VARIABLE)) {
1777: printer.p(" var");
1778: } else if (type.hasAttribute(Constants.ATT_OPTIONAL)) {
1779: printer.p(" opt");
1780: }
1781: }
1782: }
1783:
1784: /**
1785: * Print the specified tuple.
1786: *
1787: * @param tuple The tuple.
1788: * @param poly The flag for polymorphic tuples.
1789: * @param printer The printer.
1790: * @param qualified The flag for printing qualified names.
1791: * @param module The current module name, which may be <code>null</code>.
1792: */
1793: private void print(TupleT tuple, boolean poly, Printer printer,
1794: boolean qualified, String module) {
1795: String name = tuple.getName();
1796: if (!qualified
1797: || !poly
1798: || (null != module && module.equals(Utilities
1799: .getQualifier(name)))) {
1800: name = tuple.getSimpleName();
1801: }
1802:
1803: printer.p(name);
1804: final List<Type> types = tuple.getTypes();
1805: if ((null != types) && !types.isEmpty()) {
1806: printer.p(" of ");
1807: for (Iterator<Type> iter = types.iterator(); iter.hasNext();) {
1808: Type t = iter.next();
1809:
1810: if (t.resolve().isVariant()
1811: && (null == t.resolve().toVariant().getName())) {
1812: print(t, printer, false, qualified, module);
1813: if (iter.hasNext())
1814: printer.p(" * ");
1815: } else {
1816: printer.buffer();
1817: print(t, printer, false, qualified, module);
1818: if (iter.hasNext())
1819: printer.p(" * ");
1820: printer.fitMore();
1821: }
1822: }
1823: }
1824: }
1825:
1826: }
|