CSC448: Fresh Labels/Variables [2009/01/27]

When we manipulate blocks in source to source transformations, we must not confuse different local variables with the same name.

The semantics of our programming language allows us to add fresh variables and labels.

Yes, the given code is buggy, because it may give incorrect results if the original program contains, e.g., a label called "lab_6_true". Fixes?

file:clogs/transform/RenameLabelsUniquely.java [source] [doc-public] [doc-private]

00001: package clogs.transform;
00002: 
00003: import clogs.ast.*;
00004: import clogs.staticanalysis.GatherLabelsInStat;
00005: import clogs.util.List;
00006: import clogs.util.Map;
00007: import clogs.util.Optional;
00008: 
00009: 
00010: public class RenameLabelsUniquely extends Phase
00011: {
00012:   public List<ExtDecl> transform (List<ExtDecl> edecls)
00013:   {
00014:     List<ExtDecl> result = List.nil ();
00015: 
00016:     for (ExtDecl edecl : edecls) {
00017:       if (edecl instanceof Decl) {
00018:         result = result.snoc (edecl);
00019: 
00020:       } else if (edecl instanceof FunDef) {
00021:         FunDef fundef = (FunDef) edecl;
00022:         result = result.snoc (new FunDef (fundef.type, fundef.name, fundef.params, transformBody (fundef.body)));
00023: 
00024:       } else {
00025:         throw new RuntimeException ("Missing ExtDecl case: " + edecl.getClass ().getName ());
00026:       }
00027:     }
00028: 
00029:     return result;
00030:   }
00031: 
00032: 
00033:   StatCompound transformBody (StatCompound statC) {
00034:     GatherLabelsInStat glisc = new GatherLabelsInStat ();
00035:     glisc.gather (statC);
00036:     Map<String, String> labelRenaming = Map.empty ();
00037:     for (String oldLabel : glisc.labelsDefined) {
00038:       String newLabel = Fresh.getLabel (oldLabel);
00039:       labelRenaming = labelRenaming.add (oldLabel, newLabel);
00040:     }
00041: 
00042:     List<Stat> statsNew = List.nil ();
00043:     for (Stat stat : statC.stats) {
00044:       statsNew = statsNew.snoc (transformStat (labelRenaming, stat));
00045:     }
00046: 
00047:     return new StatCompound (statC.decls, statsNew);
00048:   }
00049: 
00050: 
00051:   Stat transformStat (Map<String, String> labelRenaming, Stat stat) 
00052:   {
00053:     List<String> newLabels = List.nil ();
00054:     for (String oldLabel : stat.labels) {
00055:       newLabels = newLabels.snoc (labelRenaming.get (oldLabel));
00056:     }
00057: 
00058:     if (stat instanceof StatCompound) {
00059:       StatCompound statC = (StatCompound) stat;
00060:       List<Stat> statsNew = List.nil ();
00061:       for (Stat s : statC.stats) {
00062:         statsNew = statsNew.snoc (transformStat (labelRenaming, s));
00063:       }
00064:       return new StatCompound (statC.decls, statsNew).removeLabels ().addLabels (newLabels); 
00065: 
00066:     } else if (stat instanceof StatExp) {
00067:       return stat.removeLabels ().addLabels (newLabels);
00068: 
00069:     } else if (stat instanceof StatGoto) {
00070:       StatGoto statG = (StatGoto) stat;
00071:       return new StatGoto (labelRenaming.get (statG.target)).removeLabels ().addLabels (newLabels);
00072: 
00073:     } else if (stat instanceof StatIf) {
00074:       StatIf statI = (StatIf) stat;
00075:       return new StatIf (statI.exp, transformStat (labelRenaming, statI.statT), transformStat (labelRenaming, statI.statF)).removeLabels ().addLabels (newLabels);
00076: 
00077:     } else if (stat instanceof StatReturn) {
00078:       return stat.removeLabels ().addLabels (newLabels);
00079: 
00080:     } else if (stat instanceof StatSkip) {
00081:       return stat.removeLabels ().addLabels (newLabels);
00082: 
00083:     } else if (stat instanceof StatWhile) {
00084:       StatWhile statW = (StatWhile) stat;
00085:       return new StatWhile (statW.exp, transformStat (labelRenaming, statW.stat)).removeLabels ().addLabels (newLabels);
00086: 
00087:     } else {
00088:       throw new RuntimeException ("Missing Stat case: " + stat.getClass ().getName ());
00089:     }
00090:   }
00091: }
00092: 
00093:

file:clogs/transform/Fresh.java [source] [doc-public] [doc-private]

00001: package clogs.transform;
00002: 
00003: 
00004: public class Fresh
00005: {
00006:   static int counterLabel = 0;
00007:   static int counterVar = 0;
00008:   
00009: 
00010:   public static String getLabel ()
00011:   {
00012:     return "lab_" + counterLabel++;
00013:   }
00014:   
00015: 
00016:   public static String getLabel (String previous)
00017:   {
00018:     if (previous.startsWith ("lab_")) {
00019:       return previous;
00020:     } else {
00021:       return getLabel () + "_" + previous;
00022:     }
00023:   }
00024:   
00025: 
00026:   public static String getVar ()
00027:   {
00028:     return "var_" + counterVar++;
00029:   }
00030: }
00031: