import java.security.NoSuchAlgorithmException; import java.security.MessageDigest; import java.net.*; import java.io.*; import javax.swing.*; import java.util.regex.*; import java.util.*; import java.lang.reflect.*; import java.math.*; // BigInteger import java.text.DecimalFormat; import java.lang.management.*; // for time measurement /** JavaX runner version 18 Changes to v17: -can run server-transpiled main programs for super-quick compilation (no local transpiling except for nested solvers or something) */ class _x18 { static final String version = "JavaX 18"; static boolean verbose = false, translate = false, list = false, virtualizeTranslators = true; static String translateTo = null; static boolean preferCached = false, safeOnly = false, noID = false, noPrefetch = false; static List mainTranslators = new ArrayList(); private static Map memSnippetCache = new HashMap(); private static int processesStarted, compilations; // snippet ID -> md5 private static HashMap prefetched = new HashMap(); private static File virtCache; // doesn't work yet private static Map> programCache = new HashMap>(); static boolean cacheTranslators = false; // this should work (caches transpiled translators) private static HashMap translationCache = new HashMap(); static boolean cacheTranspiledTranslators = true; // which snippets are available pre-transpiled server-side? private static Set hasTranspiledSet = new HashSet(); static boolean useServerTranspiled = true; static Object androidContext; static boolean android = isAndroid(); public static void main(String[] args) throws Exception { File ioBaseDir = new File("."), inputDir = null, outputDir = null; String src = null; List programArgs = new ArrayList(); for (int i = 0; i < args.length; i++) { String arg = args[i]; if (arg.equals("-version")) { showVersion(); return; } if (arg.equals("-sysprop")) { showSystemProperties(); return; } if (arg.equals("-v") || arg.equals("-verbose")) verbose = true; else if (arg.equals("-finderror")) verbose = true; else if (arg.equals("-offline") || arg.equalsIgnoreCase("-prefercached")) preferCached = true; else if (arg.equals("-novirt")) virtualizeTranslators = false; else if (arg.equals("-safeonly")) safeOnly = true; else if (arg.equals("-noid")) noID = true; else if (arg.equals("-nocachetranspiled")) cacheTranspiledTranslators = false; else if (arg.equals("-localtranspile")) useServerTranspiled = false; else if (arg.equals("translate")) translate = true; else if (arg.equals("list")) { list = true; virtualizeTranslators = false; // so they are silenced } else if (arg.equals("run")) { // it's the default command anyway } else if (arg.startsWith("input=")) inputDir = new File(arg.substring(6)); else if (arg.startsWith("output=")) outputDir = new File(arg.substring(7)); else if (arg.equals("with")) mainTranslators.add(new String[] {args[++i], null}); else if (translate && arg.equals("to")) translateTo = args[++i]; else if (src == null) { //System.out.println("src=" + arg); src = arg; } else programArgs.add(arg); } cleanCache(); if (useServerTranspiled) noPrefetch = true; if (src == null) src = "."; // Might actually want to write to 2 disk caches (global/per program). if (virtualizeTranslators && !preferCached) virtCache = TempDirMaker_make(); if (inputDir != null) { ioBaseDir = TempDirMaker_make(); System.out.println("Taking input from: " + inputDir.getAbsolutePath()); System.out.println("Output is in: " + new File(ioBaseDir, "output").getAbsolutePath()); copyInput(inputDir, new File(ioBaseDir, "input")); } javaxmain(src, ioBaseDir, translate, list, programArgs.toArray(new String[programArgs.size()])); if (outputDir != null) { copyInput(new File(ioBaseDir, "output"), outputDir); System.out.println("Output copied to: " + outputDir.getAbsolutePath()); } if (verbose) { // print stats System.out.println("Processes started: " + processesStarted + ", compilations: " + compilations); } } public static void javaxmain(String src, File ioDir, boolean translate, boolean list, String[] args) throws Exception { List libraries = new ArrayList(); File X = transpileMain(src, libraries); if (X == null) return; // list or run if (translate) { File to = X; if (translateTo != null) if (new File(translateTo).isDirectory()) to = new File(translateTo, "main.java"); else to = new File(translateTo); if (to != X) copy(new File(X, "main.java"), to); System.out.println("Program translated to: " + to.getAbsolutePath()); } else if (list) System.out.println(loadTextFile(new File(X, "main.java").getPath(), null)); else javax2(X, ioDir, false, false, libraries, args, null); } static File transpileMain(String src, List libraries) throws Exception { File srcDir; boolean isTranspiled = false; if (isSnippetID(src)) { prefetch(src); long id = parseSnippetID(src); srcDir = loadSnippetAsMainJava(src); if (hasTranspiledSet.contains(id)) { System.err.println("Trying pretranspiled main program: #" + id); String transpiledSrc = getServerTranspiled("#" + id); if (!transpiledSrc.isEmpty()) { srcDir = TempDirMaker_make(); saveTextFile(new File(srcDir, "main.java").getPath(), transpiledSrc); isTranspiled = true; //translationCache.put(id, new Object[] {srcDir, libraries}); } } } else { srcDir = new File(src); // if the argument is a file, it is assumed to be main.java if (srcDir.isFile()) { srcDir = TempDirMaker_make(); copy(new File(src), new File(srcDir, "main.java")); } if (!new File(srcDir, "main.java").exists()) { showVersion(); System.out.println("No main.java found, exiting"); return null; } } // translate File X = srcDir; if (!isTranspiled) { X = topLevelTranslate(X, libraries); System.err.println("Translated " + src); // save prefetch data if (isSnippetID(src)) savePrefetchData(src); } return X; } private static void prefetch(String mainSnippetID) throws IOException { if (noPrefetch) return; long mainID = parseSnippetID(mainSnippetID); String s = mainID + " " + loadTextFile(new File(userHome(), ".tinybrain/prefetch/" + mainID + ".txt").getPath(), ""); String[] ids = s.trim().split(" "); if (ids.length > 1) { String url = "http://tinybrain.de:8080/tb-int/prefetch.php?ids=" + URLEncoder.encode(s, "UTF-8"); String data = loadPage(new URL(url)); String[] split = data.split(" "); if (split.length == ids.length) for (int i = 0; i < ids.length; i++) prefetched.put(parseSnippetID(ids[i]), split[i]); } } static String _userHome; static String userHome() { if (_userHome == null) { if (android) _userHome = ((File) call(androidContext, "getFilesDir")).getAbsolutePath(); else _userHome = System.getProperty("user.home"); System.out.println("userHome: " + _userHome); } return _userHome; } private static void savePrefetchData(String mainSnippetID) throws IOException { List ids = new ArrayList(); long mainID = parseSnippetID(mainSnippetID); for (long id : memSnippetCache.keySet()) if (id != mainID) ids.add(String.valueOf(id)); saveTextFile(new File(userHome(),".tinybrain/prefetch/" + mainID + ".txt").getPath(), join(" ", ids)); } static File topLevelTranslate(File srcDir, List libraries_out) throws Exception { File X = srcDir; X = applyTranslators(X, mainTranslators, libraries_out); // translators supplied on command line (unusual) // actual inner translation of the JavaX source X = defaultTranslate(X, libraries_out); return X; } private static File defaultTranslate(File x, List libraries_out) throws Exception { x = luaPrintToJavaPrint(x); x = repeatAutoTranslate(x, libraries_out); return x; } private static File repeatAutoTranslate(File x, List libraries_out) throws Exception { while (true) { File y = autoTranslate(x, libraries_out); if (y == x) return x; x = y; } } private static File autoTranslate(File x, List libraries_out) throws Exception { String main = loadTextFile(new File(x, "main.java").getPath(), null); List lines = toLines(main); List translators = findTranslators(lines); if (translators.isEmpty()) return x; main = fromLines(lines); File newDir = TempDirMaker_make(); saveTextFile(new File(newDir, "main.java").getPath(), main); return applyTranslators(newDir, translators, libraries_out); } private static List findTranslators(List lines) { List translators = new ArrayList(); Pattern pattern = Pattern.compile("^!([0-9# \t]+)"); Pattern pArgs = Pattern.compile("^\\s*\\((.*)\\)"); for (ListIterator iterator = lines.listIterator(); iterator.hasNext(); ) { String line = iterator.next(); line = line.trim(); Matcher matcher = pattern.matcher(line); if (matcher.find()) { String[] t = matcher.group(1).split("[ \t]+"); String rest = line.substring(matcher.end()); String arg = null; if (t.length == 1) { Matcher mArgs = pArgs.matcher(rest); if (mArgs.find()) arg = mArgs.group(1); } for (String transi : t) translators.add(new String[]{transi, arg}); iterator.remove(); } } return translators; } public static List toLines(String s) { List lines = new ArrayList(); int start = 0; while (true) { int i = toLines_nextLineBreak(s, start); if (i < 0) { if (s.length() > start) lines.add(s.substring(start)); break; } lines.add(s.substring(start, i)); if (s.charAt(i) == '\r' && i+1 < s.length() && s.charAt(i+1) == '\n') i += 2; else ++i; start = i; } return lines; } private static int toLines_nextLineBreak(String s, int start) { for (int i = start; i < s.length(); i++) { char c = s.charAt(i); if (c == '\r' || c == '\n') return i; } return -1; } public static String fromLines(List lines) { StringBuilder buf = new StringBuilder(); for (String line : lines) { buf.append(line).append('\n'); } return buf.toString(); } private static File applyTranslators(File x, List translators, List libraries_out) throws Exception { for (String[] translator : translators) x = applyTranslator(x, translator[0], translator[1], libraries_out); return x; } // also takes a library private static File applyTranslator(File x, String translator, String arg, List libraries_out) throws Exception { if (verbose) System.out.println("Using translator " + translator + " on sources in " + x.getPath()); File newDir = runTranslatorOnInput(translator, null, arg, x, !verbose, libraries_out); if (!new File(newDir, "main.java").exists()) { throw new Exception("Translator " + translator + " did not generate main.java"); // TODO: show translator output } if (verbose) System.out.println("Translated with " + translator + " from " + x.getPath() + " to " + newDir.getPath()); x = newDir; return x; } private static File luaPrintToJavaPrint(File x) throws IOException { File newDir = TempDirMaker_make(); String code = loadTextFile(new File(x, "main.java").getPath(), null); code = luaPrintToJavaPrint(code); if (verbose) System.out.println(code); saveTextFile(new File(newDir, "main.java").getPath(), code); return newDir; } public static String luaPrintToJavaPrint(String code) { return ("\n" + code).replaceAll( "(\n\\s*)print (\".*\")", "$1System.out.println($2);").substring(1); } public static File loadSnippetAsMainJava(String snippetID) throws IOException { checkProgramSafety(snippetID); File srcDir = TempDirMaker_make(); saveTextFile(new File(srcDir, "main.java").getPath(), loadSnippet(snippetID)); return srcDir; } public static File loadSnippetAsMainJavaVerified(String snippetID, String hash) throws IOException { checkProgramSafety(snippetID); File srcDir = TempDirMaker_make(); saveTextFile(new File(srcDir, "main.java").getPath(), loadSnippetVerified(snippetID, hash)); return srcDir; } /** returns output dir */ private static File runTranslatorOnInput(String snippetID, String hash, String arg, File input, boolean silent, List libraries_out) throws Exception { long id = parseSnippetID(snippetID); File libraryFile = DiskSnippetCache_getLibrary(id); if (libraryFile != null) { loadLibrary(snippetID, libraries_out, libraryFile); return input; } String[] args = arg != null ? new String[]{arg} : new String[0]; File srcDir = hash == null ? loadSnippetAsMainJava(snippetID) : loadSnippetAsMainJavaVerified(snippetID, hash); long mainJavaSize = new File(srcDir, "main.java").length(); if (mainJavaSize == 0) { // no text in snippet? assume it's a library loadLibrary(snippetID, libraries_out, libraryFile); return input; } List libraries = new ArrayList(); Object[] cached = translationCache.get(id); if (cached != null) { //System.err.println("Taking translator " + snippetID + " from cache!"); srcDir = (File) cached[0]; libraries = (List) cached[1]; } else if (hasTranspiledSet.contains(id)) { System.err.println("Trying pretranspiled translator: #" + snippetID); String transpiledSrc = getServerTranspiled(snippetID); if (!transpiledSrc.isEmpty()) { srcDir = TempDirMaker_make(); saveTextFile(new File(srcDir, "main.java").getPath(), transpiledSrc); translationCache.put(id, cached = new Object[] {srcDir, libraries}); } } File ioBaseDir = TempDirMaker_make(); /*Class mainClass = programCache.get("" + parseSnippetID(snippetID)); if (mainClass != null) return runCached(ioBaseDir, input, args);*/ // Doesn't work yet because virtualized directories are hardcoded in translator... if (cached == null) { System.err.println("Translating translator #" + id); srcDir = defaultTranslate(srcDir, libraries); System.err.println("Translated translator #" + id); if (cacheTranspiledTranslators) translationCache.put(id, new Object[]{srcDir, libraries}); } boolean runInProcess = false; if (virtualizeTranslators) { if (verbose) System.out.println("Virtualizing translator"); //srcDir = applyTranslator(srcDir, "#2000351"); // I/O-virtualize the translator // that doesn't work because it recurses infinitely... // So we do it right here: String s = loadTextFile(new File(srcDir, "main.java").getPath(), null); s = s.replaceAll("new\\s+File\\(", "virtual.newFile("); s = s.replaceAll("new\\s+FileInputStream\\(", "virtual.newFileInputStream("); s = s.replaceAll("new\\s+FileOutputStream\\(", "virtual.newFileOutputStream("); s += "\n\n" + loadSnippet("#2000355"); // load class virtual // change baseDir s = s.replace("virtual_baseDir = \"\";", "virtual_baseDir = " + javaQuote(ioBaseDir.getAbsolutePath()) + ";"); // forward snippet cache (virtualized one) File dir = virtCache != null ? virtCache : DiskSnippetCache_dir; s = s.replace("static File DiskSnippetCache_dir;", "static File DiskSnippetCache_dir = new File(" + javaQuote(dir.getAbsolutePath()) + ");"); s = s.replace("static boolean preferCached = false;", "static boolean preferCached = true;"); if (verbose) { System.out.println("==BEGIN VIRTUALIZED TRANSLATOR=="); System.out.println(s); System.out.println("==END VIRTUALIZED TRANSLATOR=="); } srcDir = TempDirMaker_make(); saveTextFile(new File(srcDir, "main.java").getPath(), s); // TODO: silence translator also runInProcess = true; } return runJavaX(ioBaseDir, srcDir, input, silent, runInProcess, libraries, args, cacheTranslators ? "" + id : null); } private static String getServerTranspiled(String snippetID) throws IOException { long id = parseSnippetID(snippetID); URL url = new URL("http://tinybrain.de:8080/tb-int/get-transpiled.php?raw=1&id=" + id); return loadPage(url); } static void checkProgramSafety(String snippetID) throws IOException { if (!safeOnly) return; URL url = new URL("http://tinybrain.de:8080/tb-int/is-javax-safe.php?id=" + parseSnippetID(snippetID)); String text = loadPage(url); if (!text.startsWith("{\"safe\":\"1\"}")) throw new RuntimeException("Translator not safe: #" + parseSnippetID(snippetID)); } private static void loadLibrary(String snippetID, List libraries_out, File libraryFile) throws IOException { if (verbose) System.out.println("Assuming " + snippetID + " is a library."); if (libraryFile == null) { byte[] data = loadDataSnippetImpl(snippetID); DiskSnippetCache_putLibrary(parseSnippetID(snippetID), data); libraryFile = DiskSnippetCache_getLibrary(parseSnippetID(snippetID)); } if (!libraries_out.contains(libraryFile)) libraries_out.add(libraryFile); } private static byte[] loadDataSnippetImpl(String snippetID) throws IOException { byte[] data; try { URL url = new URL("http://eyeocr.sourceforge.net/filestore/filestore.php?cmd=serve&file=blob_" + parseSnippetID(snippetID) + "&contentType=application/binary"); System.err.println("Loading library: " + url); data = loadBinaryPage(url.openConnection()); if (verbose) System.err.println("Bytes loaded: " + data.length); } catch (FileNotFoundException e) { throw new IOException("Binary snippet #" + snippetID + " not found or not public"); } return data; } /** returns output dir */ private static File runJavaX(File ioBaseDir, File originalSrcDir, File originalInput, boolean silent, boolean runInProcess, List libraries, String[] args, String cacheAs) throws Exception { File srcDir = new File(ioBaseDir, "src"); File inputDir = new File(ioBaseDir, "input"); File outputDir = new File(ioBaseDir, "output"); copyInput(originalSrcDir, srcDir); copyInput(originalInput, inputDir); javax2(srcDir, ioBaseDir, silent, runInProcess, libraries, args, cacheAs); return outputDir; } private static void copyInput(File src, File dst) throws IOException { copyDirectory(src, dst); } public static boolean hasFile(File inputDir, String name) { return new File(inputDir, name).exists(); } public static void copyDirectory(File src, File dst) throws IOException { if (verbose) System.out.println("Copying " + src.getAbsolutePath() + " to " + dst.getAbsolutePath()); dst.mkdirs(); File[] files = src.listFiles(); if (files == null) return; for (File file : files) { File dst1 = new File(dst, file.getName()); if (file.isDirectory()) copyDirectory(file, dst1); else { if (verbose) System.out.println("Copying " + file.getAbsolutePath() + " to " + dst1.getAbsolutePath()); copy(file, dst1); } } } /** Quickly copy a file without a progress bar or any other fancy GUI... :) */ public static void copy(File src, File dest) throws IOException { FileInputStream inputStream = newFileInputStream(src); FileOutputStream outputStream = newFileOutputStream(dest); try { copy(inputStream, outputStream); inputStream.close(); } finally { outputStream.close(); } } static Object call(Object o, String method, Object... args) { try { Method m = call_findMethod(o, method, args, false); m.setAccessible(true); return m.invoke(o, args); } catch (Exception e) { throw new RuntimeException(e); } } static Object call(Class c, String method, Object... args) { try { Method m = call_findStaticMethod(c, method, args, false); m.setAccessible(true); return m.invoke(null, args); } catch (Exception e) { throw new RuntimeException(e); } } static Method call_findStaticMethod(Class c, String method, Object[] args, boolean debug) { while (c != null) { for (Method m : c.getDeclaredMethods()) { if (debug) System.out.println("Checking method " + m.getName() + " with " + m.getParameterTypes().length + " parameters");; if (!m.getName().equals(method)) { if (debug) System.out.println("Method name mismatch: " + method); continue; } if ((m.getModifiers() & Modifier.STATIC) == 0 || !call_checkArgs(m, args, debug)) continue; return m; } c = c.getSuperclass(); } throw new RuntimeException("Method '" + method + "' (static) with " + args.length + " parameter(s) not found in " + c.getName()); } static Method call_findMethod(Object o, String method, Object[] args, boolean debug) { Class c = o.getClass(); while (c != null) { for (Method m : c.getDeclaredMethods()) { if (debug) System.out.println("Checking method " + m.getName() + " with " + m.getParameterTypes().length + " parameters");; if (m.getName().equals(method) && call_checkArgs(m, args, debug)) return m; } c = c.getSuperclass(); } throw new RuntimeException("Method '" + method + "' (non-static) with " + args.length + " parameter(s) not found in " + o.getClass().getName()); } private static boolean call_checkArgs(Method m, Object[] args, boolean debug) { Class[] types = m.getParameterTypes(); if (types.length != args.length) { if (debug) System.out.println("Bad parameter length: " + args.length + " vs " + types.length); return false; } for (int i = 0; i < types.length; i++) if (!(args[i] == null || types[i].isInstance(args[i]))) { if (debug) System.out.println("Bad parameter " + i + ": " + args[i] + " vs " + types[i]); return false; } return true; } private static FileInputStream newFileInputStream(File f) throws FileNotFoundException { /*if (androidContext != null) return (FileInputStream) call(androidContext, "openFileInput", f.getPath()); else*/ return new FileInputStream(f); } private static FileOutputStream newFileOutputStream(File f) throws FileNotFoundException { /*if (androidContext != null) return (FileOutputStream) call(androidContext, "openFileOutput", f.getPath(), 0); else*/ return new FileOutputStream(f); } public static void copy(InputStream in, OutputStream out) throws IOException { byte[] buf = new byte[65536]; while (true) { int n = in.read(buf); if (n <= 0) return; out.write(buf, 0, n); } } /** writes safely (to temp file, then rename) */ public static void saveTextFile(String fileName, String contents) throws IOException { File file = new File(fileName); File parentFile = file.getParentFile(); if (parentFile != null) parentFile.mkdirs(); String tempFileName = fileName + "_temp"; FileOutputStream fileOutputStream = newFileOutputStream(new File(tempFileName)); OutputStreamWriter outputStreamWriter = new OutputStreamWriter(fileOutputStream, charsetForTextFiles); PrintWriter printWriter = new PrintWriter(outputStreamWriter); printWriter.print(contents); printWriter.close(); if (file.exists() && !file.delete()) throw new IOException("Can't delete " + fileName); if (!new File(tempFileName).renameTo(file)) throw new IOException("Can't rename " + tempFileName + " to " + fileName); } /** writes safely (to temp file, then rename) */ public static void saveBinaryFile(String fileName, byte[] contents) throws IOException { File file = new File(fileName); File parentFile = file.getParentFile(); if (parentFile != null) parentFile.mkdirs(); String tempFileName = fileName + "_temp"; FileOutputStream fileOutputStream = newFileOutputStream(new File(tempFileName)); fileOutputStream.write(contents); fileOutputStream.close(); if (file.exists() && !file.delete()) throw new IOException("Can't delete " + fileName); if (!new File(tempFileName).renameTo(file)) throw new IOException("Can't rename " + tempFileName + " to " + fileName); } public static String loadTextFile(String fileName, String defaultContents) throws IOException { if (!new File(fileName).exists()) return defaultContents; FileInputStream fileInputStream = newFileInputStream(new File(fileName)); InputStreamReader inputStreamReader = new InputStreamReader(fileInputStream, charsetForTextFiles); return loadTextFile(inputStreamReader, (int) new File(fileName).length()); } public static String loadTextFile(Reader reader, int length) throws IOException { try { char[] chars = new char[length]; int n = reader.read(chars); return new String(chars, 0, n); } finally { reader.close(); } } static File DiskSnippetCache_dir; public static void initDiskSnippetCache(File dir) { DiskSnippetCache_dir = dir; dir.mkdirs(); } // Data files are immutable, use centralized cache public static synchronized File DiskSnippetCache_getLibrary(long snippetID) throws IOException { File file = new File(getGlobalCache(), "data_" + snippetID + ".jar"); if (verbose) System.out.println("Checking data cache: " + file.getPath()); return file.exists() ? file : null; } public static synchronized String DiskSnippetCache_get(long snippetID) throws IOException { return loadTextFile(DiskSnippetCache_getFile(snippetID).getPath(), null); } private static File DiskSnippetCache_getFile(long snippetID) { return new File(DiskSnippetCache_dir, "" + snippetID); } public static synchronized void DiskSnippetCache_put(long snippetID, String snippet) throws IOException { saveTextFile(DiskSnippetCache_getFile(snippetID).getPath(), snippet); } public static synchronized void DiskSnippetCache_putLibrary(long snippetID, byte[] data) throws IOException { saveBinaryFile(new File(getGlobalCache(), "data_" + snippetID).getPath() + ".jar", data); } public static File DiskSnippetCache_getDir() { return DiskSnippetCache_dir; } public static void initSnippetCache() { if (DiskSnippetCache_dir == null) initDiskSnippetCache(getGlobalCache()); } private static File getGlobalCache() { File file = new File(userHome(), ".tinybrain/snippet-cache"); file.mkdirs(); return file; } public static String loadSnippetVerified(String snippetID, String hash) throws IOException { String text = loadSnippet(snippetID); String realHash = getHash(text.getBytes("UTF-8")); if (!realHash.equals(hash)) { String msg; if (hash.isEmpty()) msg = "Here's your hash for " + snippetID + ", please put in your program: " + realHash; else msg = "Hash mismatch for " + snippetID + ": " + realHash + " (new) vs " + hash + " - has tinybrain.de been hacked??"; throw new RuntimeException(msg); } return text; } public static String getHash(byte[] data) { return bytesToHex(getFullFingerprint(data)); } public static byte[] getFullFingerprint(byte[] data) { try { return MessageDigest.getInstance("MD5").digest(data); } catch (NoSuchAlgorithmException e) { throw new RuntimeException(e); } } public static String bytesToHex(byte[] bytes) { return bytesToHex(bytes, 0, bytes.length); } public static String bytesToHex(byte[] bytes, int ofs, int len) { StringBuilder stringBuilder = new StringBuilder(len*2); for (int i = 0; i < len; i++) { String s = "0" + Integer.toHexString(bytes[ofs+i]); stringBuilder.append(s.substring(s.length()-2, s.length())); } return stringBuilder.toString(); } public static String loadSnippet(String snippetID) throws IOException { return loadSnippet(parseSnippetID(snippetID)); } public static long parseSnippetID(String snippetID) { return Long.parseLong(shortenSnippetID(snippetID)); } private static String shortenSnippetID(String snippetID) { if (snippetID.startsWith("#")) snippetID = snippetID.substring(1); String httpBlaBla = "http://tinybrain.de/"; if (snippetID.startsWith(httpBlaBla)) snippetID = snippetID.substring(httpBlaBla.length()); return snippetID; } public static boolean isSnippetID(String snippetID) { snippetID = shortenSnippetID(snippetID); return isInteger(snippetID) && Long.parseLong(snippetID) != 0; } public static boolean isInteger(String s) { return Pattern.matches("\\-?\\d+", s); } public static String loadSnippet(long snippetID) throws IOException { String text = memSnippetCache.get(snippetID); if (text != null) return text; initSnippetCache(); text = DiskSnippetCache_get(snippetID); if (preferCached && text != null) return text; String md5 = text != null ? md5(text) : "-"; if (text != null) { String hash = prefetched.get(snippetID); if (hash != null) { if (md5.equals(hash)) { memSnippetCache.put(snippetID, text); return text; } else prefetched.remove(snippetID); // (maybe this is not necessary) } } try { /*URL url = new URL("http://tinybrain.de:8080/getraw.php?id=" + snippetID); text = loadPage(url);*/ String theURL = "http://tinybrain.de:8080/getraw.php?id=" + snippetID + "&getmd5=1&utf8=1&usetranspiled=1"; if (text != null) { //System.err.println("MD5: " + md5); theURL += "&md5=" + md5; } URL url = new URL(theURL); String page = loadPage(url); // parse & drop transpilation flag available line int i = page.indexOf('\n'); boolean hasTranspiled = page.substring(0, i).trim().equals("1"); if (hasTranspiled) hasTranspiledSet.add(snippetID); else hasTranspiledSet.remove(snippetID); page = page.substring(i+1); if (page.startsWith("==*#*==")) { // same, keep text //System.err.println("Snippet unchanged, keeping."); } else { // drop md5 line i = page.indexOf('\n'); String hash = page.substring(0, i).trim(); text = page.substring(i+1); String myHash = md5(text); if (myHash.equals(hash)) { //System.err.println("Hash match: " + hash); } else System.err.println("Hash mismatch"); } } catch (FileNotFoundException e) { e.printStackTrace(); throw new IOException("Snippet #" + snippetID + " not found or not public"); } memSnippetCache.put(snippetID, text); try { initSnippetCache(); DiskSnippetCache_put(snippetID, text); } catch (IOException e) { System.err.println("Minor warning: Couldn't save snippet to cache (" + DiskSnippetCache_getDir() + ")"); } return text; } private static String md5(String text) { try { return bytesToHex(md5impl(text.getBytes("UTF-8"))); // maybe different than the way PHP does it... } catch (UnsupportedEncodingException e) { throw new RuntimeException(e); } } public static byte[] md5impl(byte[] data) { try { return MessageDigest.getInstance("MD5").digest(data); } catch (NoSuchAlgorithmException e) { throw new RuntimeException(e); } } private static String loadPage(URL url) throws IOException { System.err.println("Loading: " + url.toExternalForm()); URLConnection con = url.openConnection(); return loadPage(con, url); } public static String loadPage(URLConnection con, URL url) throws IOException { setHeaders(con); String contentType = con.getContentType(); if (contentType == null) throw new IOException("Page could not be read: " + url); //Log.info("Content-Type: " + contentType); String charset = guessCharset(contentType); //System.err.println("Charset: " + charset); Reader r = new InputStreamReader(con.getInputStream(), charset); StringBuilder buf = new StringBuilder(); while (true) { int ch = r.read(); if (ch < 0) break; //Log.info("Chars read: " + buf.length()); buf.append((char) ch); } return buf.toString(); } public static byte[] loadBinaryPage(URLConnection con) throws IOException { setHeaders(con); return loadBinaryPage_noHeaders(con); } private static byte[] loadBinaryPage_noHeaders(URLConnection con) throws IOException { ByteArrayOutputStream buf = new ByteArrayOutputStream(); InputStream inputStream = con.getInputStream(); while (true) { int ch = inputStream.read(); if (ch < 0) break; buf.write(ch); } inputStream.close(); return buf.toByteArray(); } private static void setHeaders(URLConnection con) throws IOException { String computerID = getComputerID(); if (computerID != null) con.setRequestProperty("X-ComputerID", computerID); } public static String guessCharset(String contentType) { Pattern p = Pattern.compile("text/html;\\s+charset=([^\\s]+)\\s*"); Matcher m = p.matcher(contentType); /* If Content-Type doesn't match this pre-conception, choose default and hope for the best. */ return m.matches() ? m.group(1) : "ISO-8859-1"; } /** runs a transpiled set of sources */ public static void javax2(File srcDir, File ioBaseDir, boolean silent, boolean runInProcess, List libraries, String[] args, String cacheAs) throws Exception { if (android) javax2android(srcDir, args); else { File classesDir = TempDirMaker_make(); String javacOutput = compileJava(srcDir, libraries, classesDir); // run if (verbose) System.out.println("Running program (" + srcDir.getAbsolutePath() + ") on io dir " + ioBaseDir.getAbsolutePath() + (runInProcess ? "[in-process]" : "") + "\n"); runProgram(javacOutput, classesDir, ioBaseDir, silent, runInProcess, libraries, args, cacheAs); } } static void javax2android(File srcDir, String[] args) throws Exception { // TODO: optimize if it's a loaded snippet anyway URL url = new URL("http://tinybrain.de:8080/dexcompile.php"); URLConnection conn = url.openConnection(); String postData = "src=" + URLEncoder.encode(loadTextFile(new File(srcDir, "main.java").getPath(), null), "UTF-8"); byte[] dexData = doPostBinary(postData, conn, url); if (!isDex(dexData)) throw new RuntimeException("Dex generation error: " + dexData.length + " bytes - " + new String(dexData, "UTF-8")); System.out.println("Dex loaded: " + dexData.length + "b"); File dexDir = TempDirMaker_make(); File dexFile = new File(dexDir, System.currentTimeMillis() + ".dex"); File dexOutputDir = TempDirMaker_make(); System.out.println("Saving dex to: " + dexDir.getAbsolutePath()); try { saveBinaryFile(dexFile.getPath(), dexData); } catch (Throwable e) { System.out.println("Whoa!"); throw new RuntimeException(e); } System.out.println("Getting parent class loader."); ClassLoader parentClassLoader = //ClassLoader.getSystemClassLoader(); // does not find support jar //getClass().getClassLoader(); // Let's try this... _x18.class.getClassLoader().getParent(); // XXX ! System.out.println("Making DexClassLoader."); //DexClassLoader classLoader = new DexClassLoader(dexFile.getAbsolutePath(), dexOutputDir.getAbsolutePath(), null, // parentClassLoader); Class dcl = Class.forName("dalvik.system.DexClassLoader"); Object classLoader = dcl.getConstructors()[0].newInstance(dexFile.getAbsolutePath(), dexOutputDir.getAbsolutePath(), null, parentClassLoader); System.out.println("Loading main class."); //Class theClass = classLoader.loadClass(mainClassName); Class theClass = (Class) call(classLoader, "loadClass", "main"); System.out.println("Main class loaded."); try { set(theClass, "androidContext", androidContext); } catch (Throwable e) {} Method main = null; try { main = call_findStaticMethod(theClass, "main", new Object[]{androidContext}, false); } catch (RuntimeException e) { } System.out.println("main method for " + androidContext + " of " + theClass + ": " + main); if (main != null) { // old style main program that returns a View System.out.println("Calling main (old-style)"); Object view = main.invoke(null, androidContext); System.out.println("Calling setContentView with " + view); call(Class.forName("main"), "setContentViewInUIThread", view); //call(androidContext, "setContentView", view); System.out.println("Done."); } else { System.out.println("New-style main method running.\n\n====\n"); runMainMethod(args, theClass); } } static byte[] DEX_FILE_MAGIC = { 0x64, 0x65, 0x78, 0x0a, 0x30, 0x33, 0x35, 0x00 }; static boolean isDex(byte[] dexData) { if (dexData.length < DEX_FILE_MAGIC.length) return false; for (int i = 0; i < DEX_FILE_MAGIC.length; i++) if (dexData[i] != DEX_FILE_MAGIC[i]) return false; return true; } static byte[] doPostBinary(String urlParameters, URLConnection conn, URL url) throws IOException { // connect and do POST setHeaders(conn); conn.setDoOutput(true); OutputStreamWriter writer = new OutputStreamWriter(conn.getOutputStream()); writer.write(urlParameters); writer.flush(); byte[] contents = loadBinaryPage_noHeaders(conn); writer.close(); return contents; } static String compileJava(File srcDir, List libraries, File classesDir) throws IOException { ++compilations; // collect sources List sources = new ArrayList(); if (verbose) System.out.println("Scanning for sources in " + srcDir.getPath()); scanForSources(srcDir, sources, true); if (sources.isEmpty()) throw new IOException("No sources found"); // compile File optionsFile = File.createTempFile("javax", ""); if (verbose) System.out.println("Compiling " + sources.size() + " source(s) to " + classesDir.getPath()); String options = "-d " + bashQuote(classesDir.getPath()); writeOptions(sources, libraries, optionsFile, options); classesDir.mkdirs(); return invokeJavac(optionsFile); } private static void runProgram(String javacOutput, File classesDir, File ioBaseDir, boolean silent, boolean runInProcess, List libraries, String[] args, String cacheAs) throws Exception { // print javac output if compile failed and it hasn't been printed yet boolean didNotCompile = !didCompile(classesDir); if (verbose || didNotCompile) System.out.println(javacOutput); if (didNotCompile) return; if (runInProcess || (ioBaseDir.getAbsolutePath().equals(new File(".").getAbsolutePath()) && !silent)) { runProgramQuick(classesDir, libraries, args, cacheAs); return; } boolean echoOK = false; // TODO: add libraries to class path String bashCmd = "(cd " + bashQuote(ioBaseDir.getAbsolutePath()) + " && (java -cp " + bashQuote(classesDir.getAbsolutePath()) + " main" + (echoOK ? "; echo ok" : "") + "))"; if (verbose) System.out.println(bashCmd); String output = backtick(bashCmd); if (verbose || !silent) System.out.println(output); } static boolean didCompile(File classesDir) { return hasFile(classesDir, "main.class"); } private static void runProgramQuick(File classesDir, List libraries, String[] args, String cacheAs) throws Exception { // collect urls URL[] urls = new URL[libraries.size()+1]; urls[0] = classesDir.toURI().toURL(); for (int i = 0; i < libraries.size(); i++) urls[i+1] = libraries.get(i).toURI().toURL(); // make class loader URLClassLoader classLoader = new URLClassLoader(urls); // load JavaX main class Class mainClass = classLoader.loadClass("main"); if (cacheAs != null) programCache.put(cacheAs, mainClass); runMainMethod(args, mainClass); } static void runMainMethod(Object args, Class mainClass) throws NoSuchMethodException, IllegalAccessException, InvocationTargetException { Method main = mainClass.getMethod("main", String[].class); main.invoke(null, args); } private static String invokeJavac(File optionsFile) throws IOException { String output; try { output = invokeEcj(optionsFile); } catch (Exception e) { if (verbose) { System.err.println("ecj not found or misconfigured - using javac"); e.printStackTrace(); } output = backtick("javac " + bashQuote("@" + optionsFile.getPath())); } if (verbose) System.out.println(output); return output; } // throws ClassNotFoundException if ecj is not in classpath static String invokeEcj(File optionsFile) throws ClassNotFoundException, NoSuchMethodException, InvocationTargetException, IllegalAccessException { Class batchCompiler = getEclipseCompiler(); StringWriter writer = new StringWriter(); PrintWriter printWriter = new PrintWriter(writer); // add more eclipse options in the line below String[] args = { "@" + optionsFile.getPath(), "-source", "1.7", "-nowarn" }; Method compile = batchCompiler.getDeclaredMethod("compile", args.getClass(), PrintWriter.class, PrintWriter.class, Class.forName("org.eclipse.jdt.core.compiler.CompilationProgress")); compile.invoke(null, args, printWriter, printWriter, null); return writer.toString(); } static Class getEclipseCompiler() throws ClassNotFoundException { return Class.forName("org.eclipse.jdt.core.compiler.batch.BatchCompiler"); } private static void writeOptions(List sources, List libraries, File optionsFile, String moreOptions) throws IOException { FileWriter writer = new FileWriter(optionsFile); for (File source : sources) writer.write(bashQuote(source.getPath()) + " "); if (!libraries.isEmpty()) { List cp = new ArrayList(); for (File lib : libraries) cp.add(lib.getAbsolutePath()); writer.write("-cp " + bashQuote(join(File.pathSeparator, cp)) + " "); } writer.write(moreOptions); writer.close(); } static void scanForSources(File source, List sources, boolean topLevel) { if (source.isFile() && source.getName().endsWith(".java")) sources.add(source); else if (source.isDirectory() && !isSkippedDirectoryName(source.getName(), topLevel)) { File[] files = source.listFiles(); for (File file : files) scanForSources(file, sources, false); } } private static boolean isSkippedDirectoryName(String name, boolean topLevel) { if (topLevel) return false; // input or output ok as highest directory (intentionally specified by user, not just found by a directory scan in which case we probably don't want it. it's more like heuristics actually.) return name.equalsIgnoreCase("input") || name.equalsIgnoreCase("output"); } public static String backtick(String cmd) throws IOException { ++processesStarted; File outFile = File.createTempFile("_backtick", ""); File scriptFile = File.createTempFile("_backtick", isWindows() ? ".bat" : ""); String command = cmd + ">" + bashQuote(outFile.getPath()) + " 2>&1"; //Log.info("[Backtick] " + command); try { saveTextFile(scriptFile.getPath(), command); String[] command2; if (isWindows()) command2 = new String[] { scriptFile.getPath() }; else command2 = new String[] { "/bin/bash", scriptFile.getPath() }; Process process = Runtime.getRuntime().exec(command2); try { process.waitFor(); } catch (InterruptedException e) { throw new RuntimeException(e); } process.exitValue(); return loadTextFile(outFile.getPath(), ""); } finally { scriptFile.delete(); } } /** possibly improvable */ public static String javaQuote(String text) { return bashQuote(text); } /** possibly improvable */ public static String bashQuote(String text) { if (text == null) return null; return "\"" + text .replace("\\", "\\\\") .replace("\"", "\\\"") .replace("\n", "\\n") .replace("\r", "\\r") + "\""; } public final static String charsetForTextFiles = "UTF8"; static long TempDirMaker_lastValue; public static File TempDirMaker_make() { File dir = new File(userHome(), ".javax/" + TempDirMaker_newValue()); dir.mkdirs(); return dir; } private static long TempDirMaker_newValue() { long value; do value = System.currentTimeMillis(); while (value == TempDirMaker_lastValue); TempDirMaker_lastValue = value; return value; } public static String join(String glue, Iterable strings) { StringBuilder buf = new StringBuilder(); Iterator i = strings.iterator(); if (i.hasNext()) { buf.append(i.next()); while (i.hasNext()) buf.append(glue).append(i.next()); } return buf.toString(); } public static boolean isWindows() { return System.getProperty("os.name").contains("Windows"); } public static String makeRandomID(int length) { Random random = new Random(); char[] id = new char[length]; for (int i = 0; i< id.length; i++) id[i] = (char) ((int) 'a' + random.nextInt(26)); return new String(id); } static String computerID; public static String getComputerID() throws IOException { if (noID) return null; if (computerID == null) { File file = new File(userHome(), ".tinybrain/computer-id"); computerID = loadTextFile(file.getPath(), null); if (computerID == null) { computerID = makeRandomID(12); saveTextFile(file.getPath(), computerID); } if (verbose) System.out.println("Local computer ID: " + computerID); } return computerID; } static int fileDeletions; static void cleanCache() { if (verbose) System.out.println("Cleaning cache"); fileDeletions = 0; File javax = new File(userHome(), ".javax"); long now = System.currentTimeMillis(); File[] files = javax.listFiles(); if (files != null) for (File dir : files) { if (dir.isDirectory() && Pattern.compile("\\d+").matcher(dir.getName()).matches()) { long time = Long.parseLong(dir.getName()); long seconds = (now - time) / 1000; long minutes = seconds / 60; long hours = minutes / 60; if (hours >= 1) { //System.out.println("Can delete " + dir.getAbsolutePath() + ", age: " + hours + " h"); removeDir(dir); } } } if (verbose && fileDeletions != 0) System.out.println("Cleaned cache. File deletions: " + fileDeletions); } static void removeDir(File dir) { if (dir.getAbsolutePath().indexOf(".javax") < 0) // security check! return; for (File f : dir.listFiles()) { if (f.isDirectory()) removeDir(f); else { if (verbose) System.out.println("Deleting " + f.getAbsolutePath()); f.delete(); ++fileDeletions; } } dir.delete(); } static void showSystemProperties() { System.out.println("System properties:\n"); for (Map.Entry entry : System.getProperties().entrySet()) { System.out.println(" " + entry.getKey() + " = " + entry.getValue()); } System.out.println(); } static void showVersion() { //showSystemProperties(); boolean eclipseFound = hasEclipseCompiler(); //String platform = System.getProperty("java.vendor") + " " + System.getProperty("java.runtime.name") + " " + System.getProperty("java.version"); String platform = System.getProperty("java.vm.name") + " " + System.getProperty("java.version"); String os = System.getProperty("os.name"), arch = System.getProperty("os.arch"); System.out.println("This is " + version + "."); System.out.println("[Details: " + (eclipseFound ? "Eclipse compiler (good)" : "javac (not so good)") + ", " + platform + ", " + arch + ", " + os + "]"); } private static boolean hasEclipseCompiler() { boolean compilerFound = false; try { getEclipseCompiler(); compilerFound = true; } catch (ClassNotFoundException e) {} return compilerFound; } static boolean isAndroid() { return System.getProperty("java.vendor").toLowerCase().indexOf("android") >= 0; } static void set(Class c, String field, Object value) { try { Field f = set_findStaticField(c, field); f.setAccessible(true); f.set(null, value); } catch (Exception e) { throw new RuntimeException(e); } } static Field set_findStaticField(Class c, String field) { for (Field f : c.getDeclaredFields()) if (f.getName().equals(field) && (f.getModifiers() & Modifier.STATIC) != 0) return f; throw new RuntimeException("Static field '" + field + "' not found in " + c.getName()); } } // class _x18 modified for Android interface Function { public Object process(Object in); public void toJava_process(Code code); } interface ReversibleFunction extends Function { public Object unprocess(Object in); public void toJava_unprocess(Code code); } // generic learner (works on objects) interface Learner { public void processInOut(Object in, Object out); public Object processIn(Object in); public void toJava(Code code); public void tryAgain(); } abstract class Base { void printVars() { StringBuilder buf = new StringBuilder(); Field[] fields = getClass().getDeclaredFields(); for (Field field : fields) { if ((field.getModifiers() & Modifier.STATIC) != 0) continue; Object value; try { value = field.get(this); } catch (Exception e) { value = "?"; } if (!(buf.length() == 0)) buf.append(", "); buf.append(field.getName() + "=" + value); } System.out.println(buf.toString()); } String name() { return getClass().getName().replaceAll("^main\\$", ""); } void debug(String s) { System.out.println(name() + ": " + s); } } abstract class LearnerImpl extends Base implements Learner { public void tryAgain() { throw new RuntimeException("No try again"); } public void toJava(Code code) { main.todo(); } } class Code { StringBuilder buf = new StringBuilder(); String var = "in"; String indent = ""; List translators = new ArrayList(); List varStack = new ArrayList(); int varCounter; Code() { translators.add("!636"); } void line(String line) { buf.append(indent).append(line).append('\n'); } void indent() { indent += " "; } void unindent() { indent = indent.substring(0, indent.length()-2); } void translators(String... ids) { for (String id : ids) if (! translators.contains(id)) // space is needed otherwise translator 636 is fooled :) translators.add(id); } String getTranslators() { // TODO: We should really fix the "standard functions" translator // to properly find the main class. // // As a hack, we move it upwards (before classes adding) int i = translators.indexOf("!629"); if (i >= 0) { translators.remove(i); translators.add(0, "!629"); } return main.fromLines(translators); } String s() { return "((String) " + var + ")"; } String list() { return "((List) " + var + ")"; } void assign(String exp) { line(var + " = " + exp + ";"); } void newVar() { varStack.add(var); var = "_v" + (++varCounter); line("Object " + var + ";"); } void oldVar() { var = varStack.get(varStack.size()-1); varStack.remove(varStack.size()-1); } } public class main { // The following two fields are filled by JavaX. static Object androidContext; static String programID; static final String ALL = "#681"; static boolean classic = false; static List cases = new ArrayList(); static HashMap casesByID = new HashMap(); static boolean testJava = false, showFails, execTasks = false; static boolean collectClosest = false; // saves time static Set parseErrors = new HashSet(); static int caseIdx; static Set debuggedClasses = new HashSet(); static String strategy = "#1000464"; static String[] innerClasses={ "Case", "LSplitInput", "FDropFirstLines", "LOutSuffix", "LOutPattern", "LId", "LInputPattern", "LFixed", "LEach", "LChange", "LFindOutInIn", "LWrap", "RFJavaTok", "RFToLines", "FStringsOnly", "FNumbersOnly", "FLength", "LFixedFunction", "LTrivial", "LGetListElement", "LMath", "EscapeCase", "LCharShift", "LFirst", "LSwitch", "LMulti", "FIsString", "FCommonPrefix", "FCommonSuffix", "Matrix", "LDistinguishList", "RunnersUp", "LBox", "LBox2", "LEmptyBox", "LFixedSubstring", "LFixWhitespace", "LCertainElement", "LOneWordChanged", "LBla", "LIntersperse", "LFixedPositions", "LMap", "LPrefixSuffix", "LRemoveInputSuffix", }; static List strategyParseErrors = new ArrayList(); static Learner trying; static String user, pass; static boolean edit; public static void main(String[] args) throws Exception { keepAlive(); _x18.androidContext = androidContext; long startTime = System.currentTimeMillis(); List snippetIDs = new ArrayList(); List inputs = new ArrayList(); List inputDocs = new ArrayList(); List userCases = new ArrayList(); for (int i = 0; i < args.length; i++) { String arg = args[i]; if (arg.equals("debug")) debugOn(args[++i]); else if (arg.equals("user")) user = args[++i]; else if (arg.equals("pass")) { pass = args[++i]; args[i] = "hidden"; } else if (arg.equals("edit")) edit = true; else if (arg.equals("in")) { String in = args[++i]; //System.out.println("in=" + quote(in)); String quoteUnquote = unquote("\"" + in + "\""); //System.out.println("now in=" + quote(quoteUnquote)); inputs.add(quoteUnquote); } else if (arg.equals("in-doc")) inputDocs.add(args[++i]); else if (arg.equals("-notestjava")) testJava = false; else if (arg.equals("-testjava")) testJava = true; else if (arg.equals("-withexec")) execTasks = true; else if (arg.equals("-showfails")) showFails = true; else if (arg.equals("-classic")) classic = true; else if (arg.equals("strategy")) strategy = args[++i]; else if (arg.equals("all")) snippetIDs.add(ALL); else if (isSnippetID(arg)) snippetIDs.add(arg); else System.err.println("Unknown argument: " + arg + ", ignoring"); } if (snippetIDs.isEmpty()) { String s = loadTextFile("input/input.txt", null); if (s != null) parse(s); else parse(ALL); } for (String snippetID : snippetIDs) try { Case _case = parse(snippetID); if (_case != null) { _case.halfExamples.addAll(inputs); for (String docID : inputDocs) _case.halfExamples.add(loadSnippet(docID)); userCases.add(_case); } } catch (Throwable e) { e.printStackTrace(); parseErrors.add(snippetID); } int solved = 0, n = cases.size(), goodJava = 0; for (caseIdx = 0; caseIdx < n; caseIdx++) { Case _case = cases.get(caseIdx); try { calculate(_case); } catch (Throwable e) { e.printStackTrace(); } if (_case.winner != null) ++solved; if (_case.goodJava) ++goodJava; if (caseIdx+1 == solved) System.out.println((caseIdx+1) + " case(s) processed & solved."); else System.out.println((caseIdx+1) + " case(s) processed, " + solved + " solved."); if (testJava && goodJava < solved) System.out.println((solved-goodJava) + " case(s) with BAD JAVA."); } System.out.println(""); System.out.println("----"); List sorted = casesSortedByID(); boolean allSolved = solved == n; if (solved != 0) { System.out.println(); System.out.print("Solved: "); for (Case _case : sorted) if (_case.winner != null) System.out.print(_case.id + " "); System.out.println(); } if (testJava && solved > goodJava) { System.out.println(); System.out.print("Bad Java: "); for (Case _case : sorted) if (_case.winner != null && !_case.goodJava) System.out.print(_case.id + " "); System.out.println(); } if (!allSolved) { System.out.println(); System.out.print("Unsolved: "); for (Case _case : sorted) if (_case.winner == null) System.out.print(_case.id + " "); System.out.println(); } if (!parseErrors.isEmpty()) { System.out.print("\nParse errors: "); for (String id : parseErrors) System.out.print(id + " "); System.out.println(); } if (!strategyParseErrors.isEmpty()) System.out.println("Strategy parse errors!"); System.out.println(); if (allSolved && testJava && goodJava < solved) System.out.println("ALL SOLVED (" + solved + "), but some BAD JAVA."); else { System.out.println(allSolved ? "ALL SOLVED (" + solved + ")" : "Solved " + solved + " out of " + n + "."); if (testJava) if (goodJava == solved) System.out.println("All Java code OK" + (allSolved ? "" : " (for solved cases)") + "."); else System.out.println("Some bad Java."); else System.out.println("Java not tested."); } System.out.println(""); if (edit) { if (userCases.size() != 1) fail("Edit: More than one user case, confused"); Case _case = userCases.get(0); for (String docID : inputDocs) { Object _out = _case.processIn(loadSnippet(docID)); if (!(_out instanceof String)) fail("Case did not generate a string: " + structure(_out)); String out = (String) ( _out); String editInfo = "Solver #" + programID + " " + join(" ", args); editSnippetText(docID, out, editInfo); } } /*long time = getUserTime(); if (time >= 0) System.out.println("User time: " + formatDouble(time/1e9, 3) + "s");*/ long time = System.currentTimeMillis()-startTime; System.out.println("Real time: " + formatDouble(time/1e3, 3) + "s"); } public static String formatDouble(double d, int digits) { String format = "0."; for (int i = 0; i < digits; i++) format += "#"; String s = new DecimalFormat(format).format(d); return s.replace(',', '.'); // hack german -> english } /** Get user time in nanoseconds. */ public static long getUserTime( ) { ThreadMXBean bean = ManagementFactory.getThreadMXBean(); return bean.isCurrentThreadCpuTimeSupported() ? bean.getCurrentThreadUserTime() : -1L; } static class Case { String id; List fullExamples = new ArrayList(); List halfExamples = new ArrayList(); List examples1, examples2; Learner winner; RunnersUp runnersUp = collectClosest ? new RunnersUp() : null; boolean goodJava; List combined; int splitPoint = -1; // stats int learnersTried, retries; void split() { if (examples1 != null) return; // already done if (fullExamples.size() < 2) throw new RuntimeException("Too few examples (" + fullExamples.size() + ")"); if (splitPoint < 0) splitPoint = fullExamples.size()-1; System.out.println("Full examples: " + fullExamples.size() + ", splitPoint: " + splitPoint + ", half examples: " + halfExamples.size()); examples1 = fullExamples.subList(0, splitPoint); examples2 = fullExamples.subList(splitPoint, fullExamples.size()); } void add(Case _case) { combined.add(_case); fullExamples.addAll(_case.fullExamples); halfExamples.addAll(_case.halfExamples); } Object processIn(Object in) { return winner.processIn(in); } } static Case parse(String arg) throws Exception { try { if (arg == null) return null; arg = arg.trim(); if (arg.length() == 0) return null; Case _case = new Case(); String text; if (casesByID.containsKey(arg)) return casesByID.get(arg); if (arg.startsWith("Combine")) { _case.id = "Combine"; _case.combined = new ArrayList(); List tok = JavaTok.split(arg); List ids = new ArrayList(); for (int i = 5; i < tok.size(); i += 6) { // skip # and "and" Case case2 = parse("#" + tok.get(i)); _case.id += " #" + tok.get(i); cases.remove(case2); _case.add(case2); } addCase(_case); return _case; } if (isSnippetID(arg)) { _case.id = arg; text = loadSnippet(arg); } else { _case.id = "direct (" + shorten(arg, 10) + ")"; text = arg; } // it's a collection of cases! if (text.trim().startsWith("#") || text.trim().startsWith("Combine")) { for (String line : toLines(text)) parse(line); return null; } // it's a "Continue:" task - transform to I/O format if (text.trim().startsWith("Continue:")) { List lines = toLines(text); StringBuilder buf = new StringBuilder(); for (int i = 1; i < lines.size(); i++) { buf.append("In: " + quote("" + i) + "\n"); buf.append("Out: " + quote(lines.get(i)) + "\n"); } int numAsking = 3; for (int i = lines.size(); i < lines.size()+numAsking; i++) buf.append("In: " + quote("" + i) + "\n"); text = buf.toString(); } // it's an "Execute." task - run Java(X) and transform to I/O format if (text.trim().startsWith("Execute.")) { if (!execTasks) return null; List tok = JavaTok.split(text); StringBuilder buf = new StringBuilder(); for (int i = 5; i < tok.size(); i += 2) { if (tok.get(i).equals("-") && tok.get(i+2).equals("-")) { i += 2; buf.append("--\n"); } else { String code = unquote_fixSpaces(tok.get(i)); String result = execute("!636\n" + code); buf.append("In: " + quote(code) + "\n"); buf.append("Out: " + quote(result) + "\n"); } } text = buf.toString(); } if (text.trim().startsWith("Marking.")) { List tok = JavaTok.split(text); StringBuilder buf = new StringBuilder(); for (int i = 5; i < tok.size(); i += 2) { if (tok.get(i).equals("-") && tok.get(i+2).equals("-")) { i += 2; buf.append("--\n"); } else { String out = unquote_fixSpaces(tok.get(i)); String in = out.replace("[[", "").replace("]]", ""); buf.append("In: " + quote(in) + "\n"); buf.append("Out: " + quote(out) + "\n"); } } text = buf.toString(); } System.out.println(text); String in = null, out = null; List tok = JavaTok.split(text); for (int i = 1; i < tok.size(); i += 2) { String t = tok.get(i), t2 = i+2 < tok.size() ? tok.get(i+2) : ""; if (t.equals("-") && t2.equals("-")) { i += 2; _case.splitPoint = _case.fullExamples.size(); //System.out.println("t=" + t + ", t2= " + t2); } else if (t.toUpperCase().startsWith("I") && t2.equals("-") && tok.get(i+4).toUpperCase().equals("DOC") && tok.get(i+6).equals(":")) { // "In-Doc:" if (in != null) _case.halfExamples.add(in); i += 8; int j = findNextLine(tok, i); String inID = unquote_fixSpaces(JavaTok.join(tok.subList(i, j-1))); in = loadSnippet(inID); i = j-2; out = null; } else if (t.toUpperCase().startsWith("I") && t2.equals(":")) { // "In:" or "I:" if (in != null) _case.halfExamples.add(in); i += 4; int j = findNextLine(tok, i); in = unquote_fixSpaces(JavaTok.join(tok.subList(i, j-1))); i = j-2; out = null; } else if (t.toUpperCase().startsWith("O") && t2.equals(":")) { // "Out: " or "O: " i += 4; int j = findNextLine(tok, i); out = unquote_fixSpaces(JavaTok.join(tok.subList(i, j-1))); i = j-2; if ((in + out).indexOf('\t') >= 0) System.err.println("WARNING: Tab character used!"); System.out.println(quote(in) + " => " + quote(out)); _case.fullExamples.add(new String[] {in, out}); in = out = null; } else { int j = findNextLine(tok, i); String line = JavaTok.join(tok.subList(i, j-1)); i = j-2; System.out.println("-- Ignoring line: " + line); } } if (in != null) _case.halfExamples.add(in); addCase(_case); return _case; } catch (Throwable e) { parseErrors.add(arg); e.printStackTrace(); return null; } } static String unquote_fixSpaces(String s) { String _ = unquote(s); if (s.startsWith("[[")) _ = fixSpaces(_); return _; } // remove invisible spaces at end of line - this will otherwise confuse the engine(s) greatly... static String fixSpaces(String s) { System.out.println(quote(s)); s = s.replaceAll("[\t ]+(\r?\n)", "$1"); s = s.replaceAll("[\t ]+$", ""); //System.out.println("_fixSpaces => " + quote(s)); return s; } // i is a code-token (odd index) // return value is also a code token, or end of list static int findNextLine(List tok, int i) { while (i < tok.size() && tok.get(i-1).indexOf('\n') < 0) i += 2; return i; } static void addCase(Case _case) { cases.add(_case); casesByID.put(_case.id, _case); } static void calculate(Case _case) throws Exception { System.out.println("\n== CASE " + _case.id + " =="); _case.split(); Learner learner = findOKLearner(_case); if (learner == null) { String stat = ""; if (_case.retries != 0) stat = " + " + _case.retries + " retries"; System.out.println("\nProblem not solved (" + _case.learnersTried + " learners tried" + stat + ")"); RunnersUp ru = _case.runnersUp; if (ru != null && ru.winner != null) System.out.println("Closest result: " + quote(ru.bestResult) + " instead of " + quote(ru.expected) + " (score " + ru.bestScore + ") by " + structure(ru.winner)); } else { System.out.println("\nSolved!"); print(" " + structure(learner) + "\n"); _case.winner = learner; Code code = new Code(); if (testJava) try { learner.toJava(code); if (testJava) testJava(_case, code); // prints "GOOD JAVA" or "BAD JAVA" else System.out.println("Java:"); System.out.println(indent(" ", code.getTranslators())); System.out.println(indent(" ", code.buf.toString())); } catch (Throwable e) { System.out.println("BAD JAVA"); } for (Object in : _case.halfExamples) { Object out = learner.processIn(in); System.out.println(structure(in) + " =>! " + structure(out)); } } } static void choice_orderList(List l) { } static Learner findOKLearner(Case _case) throws Exception { List list = makeLearners(); choice_orderList(list); for (Learner learner : list) try { if (learnerOK(learner, _case)) return learner; } catch (Throwable e) { if (showFails) e.printStackTrace(); } if (_case.combined != null) { Case switchCase = makeSwitchCase(_case); calculate(switchCase); Learner learner = switchCase.winner; if (learner != null) return new LSwitch(_case, learner); } return null; } static Case makeSwitchCase(Case _case) { int i = 0; Case s = new Case(); s.id = "Switch " + _case.id; s.examples1 = new ArrayList(); s.examples2 = new ArrayList(); for (Case c : _case.combined) { ++i; for (Object[] e : c.examples1) s.examples1.add(new Object[] {e[0], String.valueOf(i)}); for (Object[] e : c.examples2) s.examples2.add(new Object[] {e[0], String.valueOf(i)}); for (Object[] e : c.fullExamples) s.fullExamples.add(new Object[] {e[0], String.valueOf(i)}); } return s; } static boolean learnerOK(Learner learner, Case _case) { trying = learner; try { Object[] _e = null; try { if (_case.examples1 == null) fail("Case not calculated: " + _case.id); ++_case.learnersTried; for (Object[] e : _case.examples1) { _e = e; learner.processInOut(e[0], e[1]); } // full validation against all examples - but starting with the unknown ones to make coding easier for learners int retry = 0; retryLoop: while (true) { int n = _case.fullExamples.size(); for (int i = 0; i < n; i++) { Object[] e = _case.fullExamples.get((i+_case.examples1.size()) % n); _e = e; Object out = learner.processIn(e[0]); if (!e[1].equals(out)) { if (_case.runnersUp != null && e[1] instanceof String && out instanceof String) _case.runnersUp.add((String) e[1], (String) out, leven((String) out, (String) e[1]), learner); if (debuggedClasses.contains(learner.getClass()) || showFails) System.out.println("[fail] " + structure(learner) + " on " + structure(e[0]) + " - got: " + structure(out) + " rather than: " + structure(e[1])); ++retry; ++_case.retries; if (retry % 1000 == 0) System.err.println("Retry " + retry); learner.tryAgain(); continue retryLoop; } } return true; // all test examples passed } } catch (Throwable e) { if (debuggedClasses.contains(learner.getClass()) || showFails) { e.printStackTrace(); System.err.println("[fail] " + structure(learner) + " on " + (_e == null ? "?" : structure(_e[0])) + " - " + e); } return false; } } finally { trying = null; } } static boolean validate(String[] example, Learner learner) { try { String out = (String) learner.processIn(example[0]); if (!example[1].equals(out)) { //System.out.println("[fail] " + learner + " on " + quote(e[0]) + " - got: " + quote(out) + " rather than: " + quote(e[1])); return false; } return true; } catch (Throwable e) { silentException(e); return false; } } static void silentException(Throwable e) { } static List makeLearners() { try { String s = isSnippetID(strategy) ? loadSnippet(strategy) : strategy; s += "\n" + combineClasses(); System.out.println("Strategy:\n" + s); List list = parseStrategy(s); if (classic) list.addAll(classicLearners()); // Endlosschleife!? return list; } catch (Exception __e) { throw __e instanceof RuntimeException ? (RuntimeException) __e : new RuntimeException(__e); }} static String combineClasses() { StringBuilder buf = new StringBuilder(); for (String s : innerClasses) { Class c = findClass(s); if (c == null) System.err.println("Warning: Class not found - " + s); else if (isSubclass(c, Learner.class)) { if (hasConstructor(c)) buf.append(getName(c) + "\n"); else for (String s2 : innerClasses) { Class c2 = findClass(s2); if (c2 != null && hasConstructor(c, c2)) buf.append(getName(c) + " " + getName(c2) + "\n"); } } } return buf.toString(); } static List parseStrategy(String strategyText) { try { List lines = toLines(strategyText); List list = new ArrayList(); for (String s : lines) try { s = s.trim(); String[] parts = s.split(" +"); if (parts.length == 0) continue; Stack stack = new Stack(); for (int i = parts.length-1; i >= 0; i--) { String p = parts[i]; Class c = findClassFlex(p); if (c == null) fail("Strategy element " + p + " not known"); Constructor ctr = c.getDeclaredConstructors()[0]; Class[] types = ctr.getParameterTypes(); if (types.length == 0) stack.add(ctr.newInstance()); else if (types.length == 1) { if (stack.isEmpty()) fail("Too few arguments for " + c.getName()); stack.add(ctr.newInstance(stack.pop())); } else if (types.length == 2) { if (stack.size() < 2) fail("Too few arguments for " + c.getName()); Object a = stack.pop(); Object b = stack.pop(); stack.add(ctr.newInstance(a, b)); } else fail("bla"); /*if (isSubclass(c, ReversibleFunction.class)) { l = new LWrap((ReversibleFunction) newInstance(c), l); continue; }*/ } list.add((Learner) stack.peek()); } catch (Throwable e) { System.err.println("Strategy parse error."); e.printStackTrace(); strategyParseErrors.add(e); } return list; } catch (Exception __e) { throw __e instanceof RuntimeException ? (RuntimeException) __e : new RuntimeException(__e); }} static List classicLearners() { List list = new ArrayList(); list.addAll(level1()); list.add(new LBox(new LMulti(level1()))); list.add(new LBox2(new LMulti(level1()))); list.add(new LChange(new FCommonPrefix(), new LOutPattern())); list.add(new LChange(new FCommonSuffix(), new LOutPattern())); list.add(new LEmptyBox(new LMulti(level1()))); list.add(new LChange(new RFToLines(), new LFixedFunction(new FLength()))); // for #1000455 list.add(new LFindOutInIn(new LFixedSubstring())); for (int I = 1; I <= 2; I++) // for #1000457 list.add(new LChange(new FDropFirstLines(I), new LMulti( new LFixWhitespace(l1()), level1()))); // for #1000458 list.add(new LFixWhitespace(l1())); return list; } static Learner l1() { return new LMulti(level1()); } static List level1() { List list = new ArrayList(); list.add(new LId()); // always good to have as included learner list.add(new LPrefixSuffix()); list.add(new LSplitInput(new LOutPattern())); list.add(new LInputPattern()); list.add(new LFixed()); list.add(new LWrap(new RFJavaTok(), new LEach(new LFixedFunction(new EscapeCase())))); list.add(new LCharShift()); list.add(new LOutSuffix(new LFirst(new LCharShift()))); list.add(new LChange(new RFJavaTok(), new LMulti( new LChange(new FStringsOnly(), new LGetListElement()), new LChange(new FNumbersOnly(), new LMath())) )); // TODO - for #1000378 list.add(new LChange(new RFJavaTok(), new LDistinguishList(new FIsString()))); list.add(new LFixedSubstring()); // of no use now it seems // list.add(new LTryPrevious()); return list; } public static String unquote(String s) { if (s.startsWith("[[") && s.endsWith("]]")) return s.substring(2, s.length()-2); else if (s.startsWith("\"") && s.endsWith("\"") && s.length() > 1) //return s.substring(1, s.length()-1).replace("\\\"", "\"").replace("\\\\", "\\"); return unescapeJavaString(s.substring(1, s.length()-1)); else return s; // return original } /** from: http://stackoverflow.com/questions/3537706/howto-unescape-a-java-string-literal-in-java, or: https://gist.github.com/uklimaschewski/6741769 Thanks! */ public static String unescapeJavaString(String st) { StringBuilder sb = new StringBuilder(st.length()); for (int i = 0; i < st.length(); i++) { char ch = st.charAt(i); if (ch == '\\') { char nextChar = (i == st.length() - 1) ? '\\' : st .charAt(i + 1); // Octal escape? if (nextChar >= '0' && nextChar <= '7') { String code = "" + nextChar; i++; if ((i < st.length() - 1) && st.charAt(i + 1) >= '0' && st.charAt(i + 1) <= '7') { code += st.charAt(i + 1); i++; if ((i < st.length() - 1) && st.charAt(i + 1) >= '0' && st.charAt(i + 1) <= '7') { code += st.charAt(i + 1); i++; } } sb.append((char) Integer.parseInt(code, 8)); continue; } switch (nextChar) { case '\\': ch = '\\'; break; case 'b': ch = '\b'; break; case 'f': ch = '\f'; break; case 'n': ch = '\n'; break; case 'r': ch = '\r'; break; case 't': ch = '\t'; break; case '\"': ch = '\"'; break; case '\'': ch = '\''; break; // Hex Unicode: u???? case 'u': if (i >= st.length() - 5) { ch = 'u'; break; } int code = Integer.parseInt( "" + st.charAt(i + 2) + st.charAt(i + 3) + st.charAt(i + 4) + st.charAt(i + 5), 16); sb.append(Character.toChars(code)); i += 5; continue; } i++; } sb.append(ch); } return sb.toString(); } static String indent(String indent, String s) { return indent + s.replace("\n", "\n" + indent); } static void debugOn(String name) { try { Class c = findClassFlex(name); debuggedClasses.add(c); Field field; while (true) try { field = c.getDeclaredField("debug"); break; } catch (NoSuchFieldException e) { c = c.getSuperclass(); } field.setBoolean(null, true); } catch (Exception e) { e.printStackTrace(); System.err.println("Cannot debug class " + name); } } static int choice(String text, int i) { return i; } // splits the input at some point, takes only one part static class LSplitInput extends LearnerImpl { int splitIdx = 1; // split after first character Learner baseLearner; LSplitInput(Learner baseLearner) { this.baseLearner = baseLearner; splitIdx = choice("LSplitInput.i", splitIdx); } public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; in = in.substring(splitIdx); baseLearner.processInOut(in, out); } public Object processIn(Object _in) { String in = (String) _in; in = in.substring(splitIdx); return baseLearner.processIn(in); } public void toJava(Code code) { if (splitIdx != 0) code.line(code.var + " = ((String) " + code.var + ").substring(" + splitIdx + ");"); baseLearner.toJava(code); } } static class FDropFirstLines implements Function { int n; FDropFirstLines(int n) { this.n = n;} public Object process(Object _in) { String in = (String)_in; for (int I=0; I < n; I++) in = in.substring(in.indexOf('\n')+1); return in; } public void toJava_process(Code code) { todo(); } } // removes common suffix from out, delegates to base learner static class LOutSuffix extends LearnerImpl { String suffixOut = ""; Learner baseLearner; LOutSuffix(Learner baseLearner) { this.baseLearner = baseLearner; } public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; if (out.endsWith("!")) suffixOut = "!"; if (out.endsWith(suffixOut)) out = out.substring(0, out.length()-suffixOut.length()); baseLearner.processInOut(in, out); } public Object processIn(Object _in) { String in = (String) _in; return baseLearner.processIn(in) + suffixOut; } public void toJava(Code code) { baseLearner.toJava(code); if (suffixOut.length() != 0) code.line(code.var + " = " + code.s() + "+" + quote(suffixOut) + ";"); } } // if input appears in output in fixed pattern static class LOutPattern extends LearnerImpl { static boolean debug; String pattern = "%!%"; public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; pattern = out.replace(in, "%!%"); if (debug) System.out.println("LOutPattern: in=" + quote(in) + ", out=" + quote(out) + ", pattern=" + quote(pattern)); } public String processIn(Object _in) { String in = (String) _in; return pattern.replace("%!%", in); } public void toJava(Code code) { code.line(code.var + " = " + quote(pattern) + ".replace(" + quote("%!%") + ", (String) " + code.var + ");"); } } // simplets learner - only knows the "id" function static class LId extends LearnerImpl { public void processInOut(Object in, Object out) { } public Object processIn(Object in) { return in; } public void toJava(Code code) { } } // for "find" tasks (e.g. "abcde" to "[[abc]]de") static class LInputPattern extends LearnerImpl { String regexp = "", findMarker1 = "[[", findMarker2 = "]]"; public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; int i = out.indexOf(findMarker1), j = out.indexOf(findMarker2, i+1); if (j < 0) return; String s = out.substring(i+2, j); regexp = s.replaceAll("\\d+", Matcher.quoteReplacement("\\d+")); System.out.println("regexp: " + regexp); } public String processIn(Object _in) { String in = (String) _in; if (regexp.length() == 0) return in; else return in.replaceAll("(" + regexp + ")", findMarker1 + "$1" + findMarker2); } public void toJava(Code code) { code.line(code.var + " = ((String) " + code.var + ").replaceAll(" + quote("(" + regexp + ")") + ", \"[[$1]]\");"); } } static class LFixed extends LearnerImpl { static boolean debug; Object value; public void processInOut(Object in, Object out) { value = out; if (debug) printVars(); } public Object processIn(Object in) { return value; } public void toJava(Code code) { code.line(code.var + " = " + quote((String) value) + ";"); } } static void fail() { throw new RuntimeException("fail"); } static void fail(String msg) { throw new RuntimeException(msg); } static void assertSameSize(List a, List b) { if (a.size() != b.size()) fail("wrong list sizes"); } // process lists in parallel // (in and out must be a list of same length) static class LEach extends LearnerImpl { static boolean debug; Learner base; LEach(Learner base) { this.base = base; } public void processInOut(Object _in, Object _out) { List in = (List) _in, out = (List) _out; assertSameSize(in, out); for (int i = 0; i < in.size(); i++) base.processInOut(in.get(i), out.get(i)); if (debug) printVars(); } public Object processIn(Object _in) { List in = (List) _in; List out = new ArrayList(); for (Object x : in) out.add(base.processIn(x)); return out; } public void toJava(Code code) { code.line("List out = new ArrayList();"); code.line("for (Object x : (List) in) {"); code.indent(); code.line("in = x;"); base.toJava(code); code.line("out.add(in);"); code.unindent(); code.line("}"); code.line("in = out;"); } } static class LChange extends LearnerImpl { Function f; Learner base; LChange(Function f, Learner base) { this.f = f; this.base = base; } public void processInOut(Object in, Object out) { in = f.process(in); base.processInOut(in, out); } public Object processIn(Object in) { in = f.process(in); return base.processIn(in); } public void toJava(Code code) { f.toJava_process(code); base.toJava(code); } } static class LFindOutInIn extends LearnerImpl { static boolean debug; Learner base; String findMarker1 = "{{", findMarker2 = "}}"; LFindOutInIn(Learner base) { this.base = base;} public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; if (out.length() == 0) out = in; else { int i = in.indexOf(out); if (i < 0) throw new RuntimeException("error"); int j = i+out.length(); out = in.substring(0, i) + findMarker1 + in.substring(i, j) + findMarker2 + in.substring(j); if (debug) System.out.println("LFindOutInIn: index=" + i); } base.processInOut(in, out); if (debug) System.out.println("LFindOutInIn: Base learned. " + base); } public Object processIn(Object _in) { if (debug) System.out.println("LFindOutInIn: processIn"); String in = (String) _in; String out = (String) base.processIn(in); int i = out.indexOf(findMarker1), j = out.indexOf(findMarker2, i)-2; String result = i < 0 ? "" : in.substring(i, j); if (debug) System.out.println("LFindOutInIn: processIn " + i + " " + j + " " + quote(result)); return result; } public void tryAgain() { base.tryAgain(); } } static class LWrap extends LearnerImpl { ReversibleFunction f; Learner base; LWrap(ReversibleFunction f, Learner base) { this.base = base; this.f = f;} public void processInOut(Object in, Object out) { in = f.process(in); out = f.process(out); base.processInOut(in, out); } public Object processIn(Object in) { in = f.process(in); in = base.processIn(in); in = f.unprocess(in); return in; } public void toJava(Code code) { f.toJava_process(code); base.toJava(code); f.toJava_unprocess(code); } } static class RFJavaTok implements ReversibleFunction { public Object process(Object in) { return JavaTok.split((String) in); } public Object unprocess(Object in) { return JavaTok.join((List) in); } public void toJava_process(Code code) { code.translators("!636", "!686"); code.line(code.var + " = JavaTok.split((String) " + code.var + ");"); } public void toJava_unprocess(Code code) { code.translators("!636", "!686"); code.line(code.var + " = JavaTok.join((List) " + code.var + ");"); } } static class RFToLines implements ReversibleFunction { public Object process(Object in) { return toLines((String) in); } public Object unprocess(Object in) { return fromLines((List) in); } public void toJava_process(Code code) { code.translators("!636", "!629"); code.assign("toLines(" + code.s() + ");"); } public void toJava_unprocess(Code code) { code.translators("!636", "!629"); code.assign("fromLines(" + code.list() + ");"); } } // works on a token list - makes a list of only the string constants (unquoted) static class FStringsOnly implements Function { static boolean debug; public Object process(Object _in) { List tok = new ArrayList(); for (String s : (List) _in) { boolean isString = s.startsWith("\"") || s.startsWith("[["); if (isString) tok.add(unquote(s)); if (debug) System.out.println("FStringsOnly - isString: " + isString + " - " + s); } return tok; } public void toJava_process(Code code) { code.translators("!629"); code.line("List tok = new ArrayList();"); code.line("for (String s : (List) " + code.var + ")"); code.line(" if (s.startsWith(\"\\\"\") || s.startsWith(\"[[\")) tok.add(unquote(s));"); code.assign("tok"); } } // works on a token list - makes a list of only the number constants static class FNumbersOnly implements Function { static boolean debug; public Object process(Object _in) { List tok = new ArrayList(); for (String s : (List) _in) { boolean isNumber = s.length() != 0 && (Character.isDigit(s.charAt(0)) || (s.charAt(0) == '-' && s.length() > 1)); if (isNumber) tok.add(s); if (debug) System.out.println("FNumbersOnly - isNumber: " + isNumber + " - " + s); } return tok; } public void toJava_process(Code code) { code.line("List tok = new ArrayList();"); code.line("for (String s : (List) " + code.var + ")"); code.line(" if (s.length() != 0 && (Character.isDigit(s.charAt(0)) || (s.charAt(0) == '-' && s.length() > 1))) tok.add(s);"); code.assign("tok"); } } static class FLength implements Function { static boolean debug; public Object process(Object in) { Object result = String.valueOf(in instanceof List ? ((List) in).size() : ((String) in).length()); if (debug) System.out.println("FLength: " + result); return result; } public void toJava_process(Code code) { code.assign("String.valueOf(" + code.var + " instanceof List ? " + code.list() + ".size() : " + code.s() + ".length())"); } } static class LFixedFunction extends LearnerImpl { Function f; LFixedFunction(Function f) { this.f = f; } public void processInOut(Object in, Object out) { } public Object processIn(Object in) { return f.process(in); } public void toJava(Code code) { f.toJava_process(code); } } // trivial stuff like taking the one element out of a 1-element list static class LTrivial extends LearnerImpl { public void processInOut(Object in, Object out) { } public Object processIn(Object in) { return ((List) in).get(0); } public void toJava(Code code) { code.assign(code.list() + ".get(0)"); } } // get element of a list at fixed index static class LGetListElement extends LearnerImpl { static boolean debug; int i; public void processInOut(Object _in, Object out) { List in = (List) _in; i = in.indexOf(out); if (debug) System.out.println("LGetListElement: " + i + " " + out); } public Object processIn(Object in) { return ((List) in).get(i); } public void toJava(Code code) { code.assign(code.list() + ".get(" + i + ")"); } } // math operations static class LMath extends LearnerImpl { static boolean debug; String allOperations = "+ - * /"; Set possibleOperations = new TreeSet(); LMath() { possibleOperations.addAll(Arrays.asList(allOperations.split(" +"))); } public void processInOut(Object _in, Object _out) { List in = (List) _in; String out = (String) _out; BigInteger[] inNumbers = getNumbers(in); BigInteger[] outNumbers = new BigInteger[] {getNumber(out)}; findOperation(inNumbers, outNumbers); if (debug) System.out.println("Operations: " + possibleOperations); } public void findOperation(BigInteger[] in, BigInteger[] out) { filterOperations(in, out); if (possibleOperations.isEmpty()) fail("tilt"); } public void filterOperations(BigInteger[] in, BigInteger[] out) { for (Iterator i = possibleOperations.iterator(); i.hasNext(); ) { String op = i.next(); BigInteger[] out2 = doOperation(op, in); if (out2 == null || !arraysEqual(out, out2)) i.remove(); // keep only matching operations } } public BigInteger[] doOperation(String op, BigInteger[] in) { op = op.intern(); try { if (in.length == 2) { BigInteger a = in[0], b = in[1], x = null; if (op == "+") x = a.add(b); else if (op == "-") x = a.subtract(b); else if (op == "*") x = a.multiply(b); else if (op == "/") x = a.divide(b); return x != null ? new BigInteger[] {x} : null; } return null; } catch (Throwable e) { return null; } } public String processIn(Object _in) { List in = (List) _in; String op = possibleOperations.iterator().next(); if (debug) System.out.println("op: " + op); BigInteger[] inNumbers = getNumbers(in); BigInteger[] outNumbers = doOperation(op, inNumbers); return outNumbers[0].toString(); } String BI = BigInteger.class.getName(); public void toJava(Code code) { String op = possibleOperations.iterator().next(); String a = "new " + BI + "((String) " + code.list() + ".get(0))"; String b = "new " + BI + "((String) " + code.list() + ".get(1))"; if (op.equals("+")) code.assign(a + ".add(" + b + ").toString()"); else todo(); } static BigInteger[] getNumbers(List in) { BigInteger[] big = new BigInteger[in.size()]; for (int i = 0; i < in.size(); i++) big[i] = new BigInteger(in.get(i)); return big; } static BigInteger getNumber(String s) { return new BigInteger(s); } static boolean arraysEqual(BigInteger[] a, BigInteger[] b) { if (a.length != b.length) return false; for (int i = 0; i < a.length; i++) if (!a[i].equals(b[i])) return false; return true; } } static class EscapeCase implements Function { static boolean debug; public Object process(Object _in) { if (debug) System.out.println("EscapeCase: " + _in); String in = (String) _in; return in.equals("case") ? "_case" : in; } public void toJava_process(Code code) { code.line("if (\"case\".equals(" + code.var + ")) " + code.var + " = " + quote("_case") + ";"); } } static class LCharShift extends LearnerImpl { int shift; public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; shift = (int) out.charAt(0) - (int) in.charAt(0); } public Object processIn(Object _in) { String in = (String) _in; char[] c = new char[in.length()]; for (int i = 0; i < c.length; i++) c[i] = (char) ((int) in.charAt(i) + shift); return new String(c); } public void toJava(Code code) { code.line("char[] c = new char[((String) " + code.var + ").length()];"); code.line("for (int i = 0; i < c.length; i++)"); code.line(" c[i] = (char) ((int) ((String) " + code.var + ").charAt(i)" + (shift < 0 ? "" + shift : "+" + shift) + ");"); code.line(code.var + " = new String(c);"); } } // applies base learner to first char of string // (or first element of list, TODO) static class LFirst extends LearnerImpl { Learner baseLearner; LFirst(Learner baseLearner) { this.baseLearner = baseLearner; } public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; if (in.length() == 0) return; String firstIn = in.substring(0, 1), firstOut = out.substring(0, 1); baseLearner.processInOut(firstIn, firstOut); } public Object processIn(Object _in) { String in = (String) _in; if (in.length() == 0) return in; String firstIn = in.substring(0, 1); return baseLearner.processIn(firstIn) + in.substring(1); } public void toJava(Code code) { code.line("if (" + code.s() + ".length() != 0) {"); code.indent(); code.line("String rest = " + code.s() + ".substring(1);"); code.line(code.var + " = " + code.s() + ".substring(0, 1);"); baseLearner.toJava(code); code.line(code.var + " = " + code.s() + "+rest;"); code.unindent(); code.line("}"); } } static Method findMainMethod(Class theClass) { for (Method method : theClass.getMethods()) if (method.getName().equals("main") && method.getParameterTypes().length == 1) return method; throw new RuntimeException("Method 'main' with 1 parameter not found in " + theClass.getName()); } // compile JavaX source and load main class static Class compileAndLoadMainClass(String src) throws Exception { File srcDir = _x18.TempDirMaker_make(); File classesDir = _x18.TempDirMaker_make(); _x18.saveTextFile(new File(srcDir, "main.java").getPath(), src); List libraries = new ArrayList(); File transpiledDir = _x18.topLevelTranslate(srcDir, libraries); String javacOutput = _x18.compileJava(transpiledDir, libraries, classesDir); System.out.println(javacOutput); URL[] urls = {classesDir.toURI().toURL()}; // make class loader URLClassLoader classLoader = new URLClassLoader(urls); // load main class Class mainClass = classLoader.loadClass("main"); return mainClass; } static Method compileJavaInToOut(Code code) { try { String java = code.buf.toString(); String prelude = /*"import java.util.*;\n\n" +*/ "public class main { public static Object main(Object in) throws Exception {\n"; String postlude = "\nreturn in;\n}}"; String src = code.getTranslators() + "\n" + prelude + java + postlude; Class mainClass = compileAndLoadMainClass(src); return findMainMethod(mainClass); } catch (Exception e) { throw new RuntimeException(e); } } static Method findCalcMethod(Class theClass) { for (Method method : theClass.getMethods()) if (method.getName().equals("calc")) return method; throw new RuntimeException("Method 'calc' not found in " + theClass.getName()); } // for simplejava stuff (execute tasks) static String execute(String src) { try { Class mainClass = compileAndLoadMainClass(src); Method m = findCalcMethod(mainClass); return String.valueOf(m.invoke(null)); } catch (Exception e) { throw new RuntimeException(e); } } static void testJava(Case _case, Code code) { try { Method m = compileJavaInToOut(code); for (Object[] e : _case.fullExamples) { String out = (String) m.invoke(null, e[0]); if (!e[1].equals(out)) { throw new RuntimeException("[fail] Java code on " + structure(e[0]) + " - got: " + structure(out) + " rather than: " + structure(e[1])); } } System.out.println("\nGOOD JAVA."); _case.goodJava = true; } catch (Throwable e) { if (showFails) e.printStackTrace(); System.out.println("\nBAD JAVA."); } } static void todo() { fail("todo"); } static class LSwitch extends LearnerImpl { Case _case; Learner switcher; LSwitch(Case _case, Learner switcher) { this._case = _case; this.switcher = switcher; } public void processInOut(Object in, Object out) { } public Object processIn(Object in) { int i = Integer.parseInt((String) switcher.processIn(in)); return _case.combined.get(i-1).winner.processIn(in); } public void toJava(Code code) { todo(); } } /*static class LTryPrevious extends LearnerImpl { List candidates = new ArrayList(); *() { for (int i = caseIdx-1; i >= 0; i--) candidates.add(cases.get(i)); } public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; for (ListIterator i = candidates.listIterator(); i.hasNext(); ) { Case case = i.next(); if (case.winner == null || !validate(new String[] {in, out}, case.winner)) i.remove(); } if (candidates.isEmpty()) fail("no previous solution found"); } public Object processIn(Object in) { return candidates.get(0).winner.processIn(in); } public void toJava(Code code) { candidates.get(0).winner.toJava(code); } }*/ static class LMulti extends LearnerImpl { static boolean debug; List candidates = new ArrayList(); LMulti(Learner... learners) { for (Learner l : learners) candidates.add(l); } LMulti(List learners) { for (Learner l : learners) candidates.add(l); } LMulti(Learner l, List ll) { candidates.add(l); candidates.addAll(ll); } public void processInOut(Object in, Object out) { if (debug) System.err.println("LMulti candidates: " + candidates.size()); for (ListIterator i = candidates.listIterator(); i.hasNext(); ) { Learner l = i.next(); try { l.processInOut(in, out); } catch (Throwable e) { if (debug) { e.printStackTrace(); System.err.println("Removing candidate: " + structure(l)); } silentException(e); i.remove(); } } if (debug) System.err.println("LMulti candidates now: " + candidates.size()); if (candidates.isEmpty()) fail("no candidates left"); } public Object processIn(Object in) { while (true) { // fails or returns eventually Learner l = candidates.get(0); if (debug) System.err.println("Using candidate: " + structure(l) + ", " + candidates.size() + " left"); try { return l.processIn(in); } catch (Throwable e) { if (debug) { e.printStackTrace(); System.err.println("Removing candidate: " + structure(l)); } silentException(e); candidates.remove(0); } } } public void tryAgain() { candidates.remove(0); } public void toJava(Code code) { candidates.get(0).toJava(code); } } static String structure(Object o) { if (o == null) return "null"; String name = o.getClass().getName(); StringBuilder buf = new StringBuilder(); if (o instanceof Collection) { for (Object x : (Collection) o) { if (!(buf.length() == 0)) buf.append(", "); buf.append(structure(x)); } return "{" + buf + "}"; } if (o instanceof String) return quote((String) o); // Need more cases? This should cover all library classes... if (name.startsWith("java.") || name.startsWith("javax.")) return String.valueOf(o); String shortName = o.getClass().getName().replaceAll("^main\\$", ""); // TODO: go to superclasses too Field[] fields = o.getClass().getDeclaredFields(); int numFields = 0; String fieldName = ""; for (Field field : fields) { if ((field.getModifiers() & Modifier.STATIC) != 0) continue; Object value; try { value = field.get(o); } catch (Exception e) { value = "?"; } fieldName = field.getName(); // special case for LMulti - show only first (current) candidate if (shortName.equals("LMulti") && field.getName().equals("candidates")) { fieldName = "candidate"; value = ((List) value).isEmpty() ? value : ((List) value).get(0); } if (value != null) { if (!(buf.length() == 0)) buf.append(", "); buf.append(fieldName + "=" + structure(value)); } ++numFields; } String b = buf.toString(); if (numFields == 1) b = b.replaceAll("^" + fieldName + "=", ""); // drop field name if only one String s = shortName; if (!(buf.length() == 0)) s += "(" + b + ")"; return s; } static class FIsString implements Function { static boolean debug; public Object process(Object _in) { String in = (String) _in; return in.startsWith("\"") || in.startsWith("[[") ? "1" : "0"; } public void toJava_process(Code code) { code.assign(code.s() + ".startsWith(\"\\\"\") || " + code.s() + ".startsWith(\"[[\") ? \"1\" : \"0\""); } } static class FCommonPrefix implements Function { static boolean debug; public Object process(Object _in) { String in = (String) _in, prefix = null; for (String line : toLines(in)) if (line.length() != 0) { prefix = prefix == null ? line : commonPrefix(prefix, line); if (debug) System.out.println("FCommonPrefix: line=" + quote(line) + ", prefix=" + quote(prefix)); } return prefix; } public void toJava_process(Code code) { todo(); } } static class FCommonSuffix implements Function { static boolean debug; public Object process(Object _in) { String in = (String) _in, suffix = null; for (String line : toLines(in)) if (line.length() != 0) { suffix = suffix == null ? line : commonSuffix(suffix, line); if (debug) System.out.println("FCommonSuffix: line=" + quote(line) + ", suffix=" + quote(suffix)); } return suffix; } public void toJava_process(Code code) { todo(); } } /*static class Pair { Object a, b; public boolean equals(Object o) { return o instanceof Pair && a.equals(((Pair) o).a) && b.equals((Pair) o).b); } public int hashCode() { return a.hashCode()+b.hashCode()*2; } }*/ static class Matrix { HashMap dataByCol = new HashMap(); void put(Object col, Object row, Object value) { //data.put(new Pair(col, row), value); getCol(col).put(row, value); } Map getCol(Object col) { Map map = dataByCol.get(col); if (map == null) dataByCol.put(col, map = new HashMap()); return map; } Object get(Object col, Object row) { //return data.get(new Pair(col, row)); return getCol(col).get(row); } Set cols() { return dataByCol.keySet(); } Set rowsFor(Object col) { return getCol(col).keySet(); } } static class LDistinguishList extends LearnerImpl { static boolean debug; Function helper; int idx; Matrix matrix = new Matrix(); LDistinguishList(Function helper) { this.helper = helper; } public void processInOut(Object _in, Object out) { List in = (List) _in; for (int i = 0; i < in.size(); i++) { Object y = helper.process(in.get(i)); matrix.put(i, y, out); } } public Object processIn(Object _in) { // find idx for (Object i : matrix.cols()) { Collection ys = matrix.rowsFor(i); if (ys.size() > 1) { idx = (Integer) i; break; } } List in = (List) _in; Object y = helper.process(in.get(idx)); return matrix.get(idx, y); } public void toJava(Code code) { List ys = new ArrayList(matrix.rowsFor(idx)); //String v = code.var; //code.newVar(); //String vy = code.var; //code.oldVar(); code.assign(code.list() + ".get(" + idx + ")"); helper.toJava_process(code); for (int i = 0; i < ys.size(); i++) { Object y = ys.get(i); if (i < ys.size()) code.line((i == 0 ? "" : "else ") + "if (" + quote((String) y) + ".equals(" + code.var + "))"); else code.line("else"); code.line(" " + code.var + " = " + quote((String) matrix.get(idx, y)) + ";"); } } } static class RunnersUp { String expected; int bestScore = -1; String bestResult; Learner winner; void add(String expected, String result, int score, Learner learner) { if (!expected.equals(this.expected) || bestScore == -1 || score < bestScore) { bestScore = score; bestResult = result; winner = learner; } this.expected = expected; } } static List casesSortedByID() { Map map = new TreeMap(); List rest = new ArrayList(); for (Case c : cases) if (isSnippetID(c.id)) map.put(parseSnippetID(c.id), c); else rest.add(c); List list = new ArrayList(map.values()); list.addAll(rest); return list; } static int leven(String s, String t) { // degenerate cases if (s.equals(t)) return 0; if (s.length() == 0) return t.length(); if (t.length() == 0) return s.length(); // create two work vectors of integer distances int[] v0 = new int[t.length() + 1]; int[] v1 = new int[t.length() + 1]; // initialize v0 (the previous row of distances) // this row is A[0][i]: edit distance for an empty s // the distance is just the number of characters to delete from t for (int i = 0; i < v0.length; i++) v0[i] = i; for (int i = 0; i < s.length(); i++) { // calculate v1 (current row distances) from the previous row v0 // first element of v1 is A[i+1][0] // edit distance is delete (i+1) chars from s to match empty t v1[0] = i + 1; // use formula to fill in the rest of the row for (int j = 0; j < t.length(); j++) { int cost = s.charAt(i) == t.charAt(j) ? 0 : 1; v1[j + 1] = Math.min(Math.min(v1[j] + 1, v0[j + 1] + 1), v0[j] + cost); } // copy v1 (current row) to v0 (previous row) for next iteration /*for (int j = 0; j < v0.length; j++) v0[j] = v1[j];*/ // swap arrays int[] v = v1; v1 = v0; v0 = v; } // for array copying: // return v1[t.length()]; // for array swapping: return v0[t.length()]; } // leven (Levenshtein distance function) // These end up inside the main class static class LBox extends LearnerImpl { static boolean debug; Learner middleLearner; char topChar, bottomChar; LBox(Learner middleLearner) { this.middleLearner = middleLearner; } // An optimization, but a bit of a dangerous one: /*public void forwardSecretExample(Object _in, Object _out) { String in = (String) _in, out = (String) _out; L l = toLines(out); String middle = l.get(2); middleLearner.processInOut(in, middle); }*/ public void tryAgain() { middleLearner.tryAgain(); } public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; List l = toLines(out); String middle = l.get(2); middleLearner.processInOut(in, middle); topChar = l.get(1).charAt(0); bottomChar = l.get(3).charAt(0); } public Object processIn(Object in) { String middle = (String) middleLearner.processIn(in); return "\n" + repeat(topChar, middle.length()) + "\n" + middle + "\n" + repeat(bottomChar, middle.length()) + "\n"; } static String repeat(char c, int n) { char[] chars = new char[n]; for (int i = 0; i < n; i++) chars[i] = c; return new String(chars); } public void toJava(Code code) { todo(); } } static class LBox2 extends LearnerImpl { static boolean debug; Learner middleLearner; char topChar, bottomChar, tlChar, trChar, blChar, brChar; LBox2(Learner middleLearner) { this.middleLearner = middleLearner; } public void tryAgain() { middleLearner.tryAgain(); } public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; List l = toLines(out); String middle = l.get(2); if (debug) System.out.println("Forwarding to middle learner: " + quote(in) + " => " + quote(middle)); middleLearner.processInOut(in, middle); String top = l.get(1), bottom = l.get(3); tlChar = top.charAt(0); topChar = top.charAt(1); trChar = top.charAt(top.length()-1); blChar = bottom.charAt(0); bottomChar = bottom.charAt(1); brChar = bottom.charAt(bottom.length()-1); } public Object processIn(Object in) { String middle = (String) middleLearner.processIn(in); return "\n" + tlChar + repeat(topChar, middle.length()-2) + trChar + "\n" + middle + "\n" + blChar + repeat(bottomChar, middle.length()-2) + brChar + "\n"; } static String repeat(char c, int n) { char[] chars = new char[n]; for (int i = 0; i < n; i++) chars[i] = c; return new String(chars); } public void toJava(Code code) { todo(); } } // Box learners // These end up inside the main class static class LEmptyBox extends LearnerImpl { static boolean debug; Learner inputLearner; char c; LEmptyBox(Learner inputLearner) { this.inputLearner = inputLearner;} public void tryAgain() { inputLearner.tryAgain(); } public void processInOut(Object in, Object _out) { String out = (String) _out; List l = toLines(out); int w = l.get(1).length(), h = l.size()-1; String input = w + "*" + h; if (debug) System.out.println("LEmptyBox: Feeding to input learner: " + in + " => " + input); inputLearner.processInOut(in, input); if (debug) System.out.println("Input learner: " + structure(inputLearner)); c = l.get(1).charAt(0); if (debug) System.out.println("LEmptyBox: c=" + c); } public Object processIn(Object in) { String input = (String) inputLearner.processIn(in); if (debug) System.out.println("LEmptyBox: in=" + in + ", input=" + input); String[] split = input.split("\\*"); int w = Integer.parseInt(split[0]), h = Integer.parseInt(split[1]); StringBuilder buf = new StringBuilder(); buf.append("\n"); buf.append(repeat(c, w) + "\n"); for (int y = 1; y < h-1; y++) buf.append(c + repeat(' ', w-2) + c + "\n"); buf.append(repeat(c, w) + "\n"); return buf.toString(); } static String repeat(char c, int n) { char[] chars = new char[n]; for (int i = 0; i < n; i++) chars[i] = c; return new String(chars); } public void toJava(Code code) { todo(); } } // Empty box learner // for "find" tasks (e.g. "abcde" to "[[abc]]de") static class LFixedSubstring extends LearnerImpl { static boolean debug; String findMarker1 = "{{", findMarker2 = "}}"; int i, j; public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; i = out.indexOf(findMarker1); j = out.indexOf(findMarker2, i)-2; if (debug && j >= 0) { boolean correct = in.substring(i, j).equals(out.substring(i+2, j+2)); System.out.println("LFixedSubstring: i, j = " + i + ", " + j + " " + correct + " " + quote(in.substring(i, j))); } } public String processIn(Object _in) { String in = (String) _in; return in.substring(0, i) + findMarker1 + in.substring(i, j) + findMarker2 + in.substring(j); } } static void print(Object o) { System.out.println(o); } // These end up inside the main class static class LFixWhitespace extends LearnerImpl { static boolean debug; Learner base; String s; LFixWhitespace(Learner base) { this.base = base;} public void tryAgain() { base.tryAgain(); } public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; int i = count(in), j = count(out); in = in.substring(i); s = out.substring(0, j); out = out.substring(j); if (debug) System.out.println("LFixWhitespace: Feeding to input learner: " + in + " => " + out); base.processInOut(in, out); } public Object processIn(Object _in) { String in = (String) _in; int i = count(in); in = in.substring(i); in = (String) base.processIn(in); in = s + in; return in; } int count(String s) { int I = 0; while (I < s.length () && "\r\n\t ".indexOf(s.charAt(I)) >= 0) ++I; return I; } } // LFixWhiteSpace static Object newInstance(Class c, Object... args) { try { Constructor m = findConstructor(c, args); m.setAccessible(true); return m.newInstance(args); } catch (Exception __e) { throw __e instanceof RuntimeException ? (RuntimeException) __e : new RuntimeException(__e); }} static boolean hasConstructor(Class c, Object... args) { for (Constructor m : c.getDeclaredConstructors()) { if (!checkArgs(m.getParameterTypes(), args, false)) continue; return true; } return false; } static Constructor findConstructor(Class c, Object... args) { for (Constructor m : c.getDeclaredConstructors()) { if (!checkArgs(m.getParameterTypes(), args, false)) continue; return m; } throw new RuntimeException("Constructor with " + args.length + " matching parameter(s) not found in " + c.getName()); } static Class findClass(String name) { try { for (String c : innerClasses) if (c.equalsIgnoreCase(name)) return Class.forName("main$" + c); return null; } catch (Exception __e) { throw __e instanceof RuntimeException ? (RuntimeException) __e : new RuntimeException(__e); }} static boolean isSubclass(Class a, Class b) { return b.isAssignableFrom(a); } static boolean checkArgs(Class[] types, Object[] args, boolean debug) { if (types.length != args.length) { if (debug) System.out.println("Bad parameter length: " + args.length + " vs " + types.length); return false; } for (int i = 0; i < types.length; i++) if (!(args[i] == null || types[i].isInstance(args[i]))) { if (debug) System.out.println("Bad parameter " + i + ": " + args[i] + " vs " + types[i]); return false; } return true; } // finds a fixed element, e.g. a Java token static class LCertainElement extends LearnerImpl { static boolean debug; ReversibleFunction f; // e.g. JavaTok String element; LCertainElement(ReversibleFunction f) { this.f = f;} public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; Set set = new HashSet(getMarked(out)); if (debug) System.out.println("LCertainElement: set=" + set); if (set.size() == 1) element = set.iterator().next(); if (debug) System.out.println("LCertainElement: element=" + element); } public Object processIn(Object _in) { List l = (List) f.process(_in); List l2 = new ArrayList(); for (String x : l) l2.add(x.equals(element) ? "[[" + x + "]]" : x); return f.unprocess(l2); } static List getFindMarkers2(String s) { List l = new ArrayList(); int i = 0; while (i < s.length()) { int j = s.indexOf("[[", i); if (j < 0) break; int k = s.indexOf("]]", j+2); if (k < 0) break; l.add(j); l.add(k+2); i = k+2; } return l; } static List getMarked(String s) { List l = getFindMarkers2(s); List result = new ArrayList(); for (int i = 0; i < l.size(); i += 2) result.add(s.substring(l.get(i)+2, l.get(i+1)-2)); return result; } } // LCertainElement static Class findClassFlex(String p) { Class c = findClass(p); if (c == null) c = findClass("L" + p); if (c == null) c = findClass("F" + p); if (c == null) c = findClass("RF" + p); return c; } static class LOneWordChanged extends LearnerImpl { static boolean debug; Function preprocessor; // e.g. JavaTok List lastIn; // only while learning String lastOut; // only while learning int index; String outPattern; LOneWordChanged(Function preprocessor) { this.preprocessor = preprocessor;} public void processInOut(Object _in, Object _out) { if (debug) System.out.println("LOneWordChanged: i/o " + _in + " " + _out); String in = (String) _in, out = (String) _out; List l = (List) preprocessor.process(_in); lastIn = l; lastOut = out; } public Object processIn(Object _in) { if (debug) System.out.println("LOneWordChanged: i " + _in); List l = (List) preprocessor.process(_in); if (outPattern == null) { if (l.size() != lastIn.size()) fail(); for (int i = 0; i < l.size(); i++) if (!l.get(i).equals(lastIn.get(i))) { index = i; String word = lastIn.get(index); outPattern = lastOut.replace(word, "{*}"); // delete learning data lastIn = null; lastOut = null; break; } if (outPattern == null) { if (debug) System.out.println("LOneWordChanged: last=" + lastIn + ", this=" + l); fail("not applicable - all words identical"); } } if (debug) System.out.println("LOneWordChanged: index=" + index + ", outPattern=" + quote(outPattern)); String word = l.get(index); return outPattern.replace("{*}", word); } static List getFindMarkers2(String s) { List l = new ArrayList(); int i = 0; while (i < s.length()) { int j = s.indexOf("[[", i); if (j < 0) break; int k = s.indexOf("]]", j+2); if (k < 0) break; l.add(j); l.add(k+2); i = k+2; } return l; } static List getMarked(String s) { List l = getFindMarkers2(s); List result = new ArrayList(); for (int i = 0; i < l.size(); i += 2) result.add(s.substring(l.get(i)+2, l.get(i+1)-2)); return result; } } // LOneWordChanged static class LBla extends LearnerImpl { static boolean debug; String inPattern, outPattern; public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; int i = in.indexOf("bla"), j = out.indexOf("bla"); if (i < 0 || j < 0) fail(); inPattern = "^" + patternQuote(in.substring(0, i)) + "(.+)" + patternQuote(in.substring(i+3)) + "$"; outPattern = Matcher.quoteReplacement(out.substring(0, j)) + "$1" + Matcher.quoteReplacement(out.substring(j+3)); } public Object processIn(Object _in) { String in = (String) _in; return in.replaceAll(inPattern, outPattern); } } // LBla static String shorten(String s, int max) { return s.length() <= max ? s : s.substring(0, Math.min(s.length(), max)) + "..."; } // for stuff like #1000478 static class LIntersperse extends LearnerImpl { static boolean debug; ReversibleFunction preprocessor; // e.g. JavaTok List outPrefix, outSuffix, filler; LIntersperse(ReversibleFunction preprocessor) { this.preprocessor = preprocessor;} public void processInOut(Object _in, Object _out) { if (debug) debug("i/o " + _in + " " + _out); List in = (List) ( preprocessor.process(_in)); List out = (List) ( preprocessor.process(_out)); int i = out.indexOf(in.get(1)); outPrefix = out.subList(0, i); int j = out.lastIndexOf(in.get(in.size()-2)); outSuffix = out.subList(j+1, out.size()); int newLength = j-i+1; int realOldLength = (in.size()-1)/2; /*int intersperse = 0; if (realOldLength > 1) intersperse = newLength-realOldLength*3-1;*/ int intersperse = 3; // just assume this for now if (realOldLength > 1) filler = out.subList(i+1, i+1+intersperse); if (debug) debug("oldLength= " + in.size() + ", newLength=" + newLength +", realOldLength=" + realOldLength + ", intersperse=" + intersperse + ", filler length=" + (filler == null ? 0 : filler.size())); } public Object processIn(Object _in) { List l = (List) ( preprocessor.process(_in)); if (debug) debug("i " + structure(l)); List list = new ArrayList(); list.addAll(outPrefix); if (debug) debug("ranging from " + 1 + " to " + (l.size()-2)); for (int i = 1; i < l.size()-1; i += 2) { list.add(l.get(i)); if (i < l.size()-2) list.addAll(filler); } list.addAll(outSuffix); Object out = preprocessor.unprocess(list); if (debug) debug("output: " + structure(list) + " = " + structure(out)); return out; } } // LIntersperse static String getName(Class c) { return c.getName().replaceAll("^main\\$", ""); } static void keepAlive() { Thread _t = new Thread() { public void run() { try { Object printed = null; while (true) { Object t = trying; Thread.sleep(1000); if (t != null && t == trying && printed != t) { // still trying System.err.println("* "+ structure(t)); printed = t; } else printed = null; } } catch (Exception _e) { throw _e instanceof RuntimeException ? (RuntimeException) _e : new RuntimeException(_e); } } }; _t.setDaemon(true); _t.start(); } // for stuff like #1000349 static class LFixedPositions extends LearnerImpl { static boolean debug; Map map = new TreeMap(); public void processInOut(Object _in, Object _out) { // Only looks at out... funny, eh? String out = (String) ( _out); for (int i = 0; i < out.length(); i++) { String s = map.get(i); String c = out.substring(i, i+1); if (s == null) map.put(i, c); else if (s.equals("")) { } else if (!s.equals(c)) map.put(i, ""); // TILT } for (int i : map.keySet()) if (i >= out.length()) map.put(i, ""); } public Object processIn(Object _in) { String in = (String) ( _in); List l = new ArrayList(); for (int i = 0; i < in.length(); i++) l.add(in.substring(i, i+1)); for (int i : map.keySet()) { String s = map.get(i); if (!s.equals("")) { while (i >= l.size()) l.add(" "); l.set(i, s); } } return join("", l); } } // LFixedPositions // for stuff like #1000351 static class LMap extends LearnerImpl { static boolean debug; Map map = new TreeMap(); public void processInOut(Object _in, Object _out) { List in = (List) ( _in); List out = (List) ( _out); if (in.size() != out.size()) fail(); for (int i = 0; i < in.size(); i++) { String a = in.get(i), b = out.get(i); if (!a.equals(b)) map.put(a, b); } } public Object processIn(Object _in) { List in = (List) ( _in); List out = new ArrayList(); for (int i = 0; i < in.size(); i++) { String a = in.get(i), b = map.get(a); out.add(b != null ? b : a); } return out; } } // LMap // learns to exchange common prefixes and suffixes. // maybe it's not perfect... see #1000491 for a problem case static class LPrefixSuffix extends LearnerImpl { static boolean debug; String prefixIn, suffixIn, prefixOut, suffixOut; public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; updateIn(in); prefixOut = prefixOut == null ? out : commonPrefix(prefixOut, out); suffixOut = suffixOut == null ? out : commonSuffix(suffixOut, out); if (debug) printState("processInOut(" + quote(in) + ", " + quote(out) + ")"); } void updateIn(String in) { prefixIn = prefixIn == null ? in : commonPrefix(prefixIn, in); suffixIn = suffixIn == null ? in : commonSuffix(suffixIn, in); if (debug) printState("updateIn(" + quote(in) + ")"); } public String processIn(Object _in) { String in = (String) _in; //System.out.println("[before last info] " + quote(prefixIn) + " " + quote(suffixIn) + " " + quote(prefixOut) + " " + quote(suffixOut)); //System.out.println("[last info] " + quote(in)); // use latest information String p = prefixIn, s = suffixIn; updateIn(in); prefixOut = prefixOut.substring(0, prefixOut.length()-(p.length()-prefixIn.length())); suffixOut = suffixOut.substring(s.length()-suffixIn.length()); //System.out.println("[after last info] " + quote(prefixIn) + " " + quote(suffixIn) + " " + quote(prefixOut) + " " + quote(suffixOut)); String core = in.substring(prefixIn.length(), in.length()-suffixIn.length()); return prefixOut + core + suffixOut; } public void toJava(Code code) { if (prefixIn.length() != 0 || suffixIn.length() != 0) code.line(code.var + " = ((String) " + code.var + ").substring(" + prefixIn.length() + ", " + code.s() + ".length()-" + suffixIn.length() + ");"); if (prefixOut.length() != 0 || suffixOut.length() != 0) code.line(code.var + " = " + quote(prefixOut) + " + " + code.var + " + " + quote(suffixOut) + ";"); } void printState(String text) { System.out.println(text); printVars(); } } // LPrefixSuffix // learns to remove input suffixes. static class LRemoveInputSuffix extends LearnerImpl { static boolean debug; String suffix; static boolean failFast = false; public void processInOut(Object _in, Object _out) { String in = (String) _in, out = (String) _out; if (!in.startsWith(out)) fail(); suffix = overwrite(suffix, in.substring(out.length())); } public String processIn(Object _in) { String in = (String) _in; if (!in.endsWith(suffix)) if (failFast) fail(); else return in; return in.substring(0, in.length()-suffix.length()); } } // LRemoveInputSuffix static T overwrite(T existing, T newValue) { if (existing != null && !existing.equals(newValue)) fail("Overwrite"); return newValue; } static void getPass() { try { if (user != null) { File pwFile = new File(_x18.userHome(), ".javax/pw-" + user); if (pass == null) { pass = toLines(readTextFile(pwFile, "")).get(0).trim(); //System.out.println("Pass: " + quote(pass)); if (pass != null) System.out.println("Password read from " + pwFile.getAbsolutePath()); } if (pass == null) System.out.println("You can put your password in: " + pwFile.getAbsolutePath()); } } catch (Exception __e) { throw __e instanceof RuntimeException ? (RuntimeException) __e : new RuntimeException(__e); }} static void editSnippetText(String docID, String newText, String editInfo) { try { getPass(); System.out.println("Editing " + docID); URL url = new URL("http://tinybrain.de:8080/tb-int/auto-edit.php"); String postData = "user=" + urlencode(user) + "&pass=" + urlencode(pass) + "&id=" + urlencode(docID) + "&text=" + urlencode(newText) + "&editinfo=" + urlencode(editInfo); System.out.println(postData); String result = doPost(postData, url.openConnection(), url); System.out.println("Edit result: " + result); } catch (Exception __e) { throw __e instanceof RuntimeException ? (RuntimeException) __e : new RuntimeException(__e); }} static String urlencode(String s) { try { return URLEncoder.encode(unnull(s), "UTF-8"); } catch (Exception __e) { throw __e instanceof RuntimeException ? (RuntimeException) __e : new RuntimeException(__e); }} static String doPost(String urlParameters, URLConnection conn, URL url) throws IOException { // connect and do POST conn.setDoOutput(true); OutputStreamWriter writer = new OutputStreamWriter(conn.getOutputStream()); writer.write(urlParameters); writer.flush(); String contents = loadPage(conn, url); writer.close(); return contents; } /** writes safely (to temp file, then rename) */ public static void saveTextFile(String fileName, String contents) throws IOException { File file = new File(fileName); File parentFile = file.getParentFile(); if (parentFile != null) parentFile.mkdirs(); String tempFileName = fileName + "_temp"; FileOutputStream fileOutputStream = new FileOutputStream(tempFileName); OutputStreamWriter outputStreamWriter = new OutputStreamWriter(fileOutputStream, "UTF-8"); PrintWriter printWriter = new PrintWriter(outputStreamWriter); printWriter.print(contents); printWriter.close(); if (file.exists() && !file.delete()) throw new IOException("Can't delete " + fileName); if (!new File(tempFileName).renameTo(file)) throw new IOException("Can't rename " + tempFileName + " to " + fileName); } public static String loadTextFile(String fileName, String defaultContents) throws IOException { if (!new File(fileName).exists()) return defaultContents; FileInputStream fileInputStream = new FileInputStream(fileName); InputStreamReader inputStreamReader = new InputStreamReader(fileInputStream, "UTF-8"); return loadTextFile(inputStreamReader); } public static String loadTextFile(Reader reader) throws IOException { StringBuilder builder = new StringBuilder(); try { BufferedReader bufferedReader = new BufferedReader(reader); String line; while ((line = bufferedReader.readLine()) != null) builder.append(line).append('\n'); } finally { reader.close(); } return builder.length() == 0 ? "" : builder.substring(0, builder.length()-1); } public static String readTextFile(String fileName, String defaultContents) throws IOException { return loadTextFile(fileName, defaultContents); } public static String readTextFile(File file, String defaultContents) throws IOException { return loadTextFile(file.getPath(), defaultContents); } public static List toLines(String s) { List lines = new ArrayList(); int start = 0; while (true) { int i = toLines_nextLineBreak(s, start); if (i < 0) { if (s.length() > start) lines.add(s.substring(start)); break; } lines.add(s.substring(start, i)); if (s.charAt(i) == '\r' && i+1 < s.length() && s.charAt(i+1) == '\n') i += 2; else ++i; start = i; } return lines; } private static int toLines_nextLineBreak(String s, int start) { for (int i = start; i < s.length(); i++) { char c = s.charAt(i); if (c == '\r' || c == '\n') return i; } return -1; } public static String fromLines(List lines) { StringBuilder buf = new StringBuilder(); for (String line : lines) { buf.append(line).append('\n'); } return buf.toString(); } static boolean preferCached = false; public static String loadSnippet(String snippetID) throws IOException { return loadSnippet(parseSnippetID(snippetID), preferCached); } public static String loadSnippet(String snippetID, boolean preferCached) throws IOException { return loadSnippet(parseSnippetID(snippetID), preferCached); } public static long parseSnippetID(String snippetID) { return Long.parseLong(shortenSnippetID(snippetID)); } private static String shortenSnippetID(String snippetID) { if (snippetID.startsWith("#")) snippetID = snippetID.substring(1); String httpBlaBla = "http://tinybrain.de/"; if (snippetID.startsWith(httpBlaBla)) snippetID = snippetID.substring(httpBlaBla.length()); return snippetID; } public static boolean isSnippetID(String snippetID) { snippetID = shortenSnippetID(snippetID); return isInteger(snippetID) && Long.parseLong(snippetID) != 0; } public static boolean isInteger(String s) { return Pattern.matches("\\-?\\d+", s); } public static String loadSnippet(long snippetID, boolean preferCached) throws IOException { if (preferCached) { initSnippetCache(); String text = DiskSnippetCache_get(snippetID); if (text != null) return text; } String text; try { URL url = new URL("http://tinybrain.de:8080/getraw.php?id=" + snippetID); text = loadPage(url); } catch (FileNotFoundException e) { throw new IOException("Snippet #" + snippetID + " not found or not public"); } try { initSnippetCache(); DiskSnippetCache_put(snippetID, text); } catch (IOException e) { System.err.println("Minor warning: Couldn't save snippet to cache (" + DiskSnippetCache_getDir() + ")"); } return text; } static File DiskSnippetCache_dir; public static void initDiskSnippetCache(File dir) { DiskSnippetCache_dir = dir; dir.mkdirs(); } public static synchronized String DiskSnippetCache_get(long snippetID) throws IOException { return loadTextFile(DiskSnippetCache_getFile(snippetID).getPath(), null); } private static File DiskSnippetCache_getFile(long snippetID) { return new File(DiskSnippetCache_dir, "" + snippetID); } public static synchronized void DiskSnippetCache_put(long snippetID, String snippet) throws IOException { saveTextFile(DiskSnippetCache_getFile(snippetID).getPath(), snippet); } public static File DiskSnippetCache_getDir() { return DiskSnippetCache_dir; } public static void initSnippetCache() { if (DiskSnippetCache_dir == null) initDiskSnippetCache(new File(System.getProperty("user.home"), ".tinybrain/snippet-cache")); } public static String commonPrefix(String a, String b) { int i = 0; while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) ++i; return a.substring(0, i); } public static String commonSuffix(String a, String b) { int i = 0; while (i < a.length() && i < b.length() && a.charAt(a.length()-1-i) == b.charAt(b.length()-1-i)) ++i; return a.substring(a.length()-i); } public static String quote(String s) { if (s == null) return "null"; return "\"" + s.replace("\\", "\\\\").replace("\"", "\\\"").replace("\r", "\\r").replace("\n", "\\n") + "\""; } public static String bytesToHex(byte[] bytes) { return bytesToHex(bytes, 0, bytes.length); } public static String bytesToHex(byte[] bytes, int ofs, int len) { StringBuilder stringBuilder = new StringBuilder(len*2); for (int i = 0; i < len; i++) { String s = "0" + Integer.toHexString(bytes[ofs+i]); stringBuilder.append(s.substring(s.length()-2, s.length())); } return stringBuilder.toString(); } public static byte[] loadBinaryPage(URLConnection con) throws IOException { //setHeaders(con); ByteArrayOutputStream buf = new ByteArrayOutputStream(); InputStream inputStream = con.getInputStream(); int n = 0; while (true) { int ch = inputStream.read(); if (ch < 0) break; buf.write(ch); if (++n % 100000 == 0) System.err.println(" " + n + " bytes loaded."); } inputStream.close(); return buf.toByteArray(); } /** writes safely (to temp file, then rename) */ public static void saveBinaryFile(String fileName, byte[] contents) throws IOException { File file = new File(fileName); File parentFile = file.getParentFile(); if (parentFile != null) parentFile.mkdirs(); String tempFileName = fileName + "_temp"; FileOutputStream fileOutputStream = new FileOutputStream(tempFileName); fileOutputStream.write(contents); fileOutputStream.close(); if (file.exists() && !file.delete()) throw new IOException("Can't delete " + fileName); if (!new File(tempFileName).renameTo(file)) throw new IOException("Can't rename " + tempFileName + " to " + fileName); } public static String loadPage(String url) throws IOException { if (url.indexOf("://") < 0) url = "http://" + url; return loadPage(new URL(url)); } public static String loadPage(URL url) throws IOException { System.out.println("Loading: " + url.toExternalForm()); URLConnection con = url.openConnection(); return loadPage(con, url); } public static String loadPage(URLConnection con, URL url) throws IOException { String contentType = con.getContentType(); if (contentType == null) throw new IOException("Page could not be read: " + url); //Log.info("Content-Type: " + contentType); String charset = loadPage_guessCharset(contentType); Reader r = new InputStreamReader(con.getInputStream(), charset); StringBuilder buf = new StringBuilder(); while (true) { int ch = r.read(); if (ch < 0) break; //Log.info("Chars read: " + buf.length()); buf.append((char) ch); } return buf.toString(); } static String loadPage_guessCharset(String contentType) { Pattern p = Pattern.compile("text/html;\\s+charset=([^\\s]+)\\s*"); Matcher m = p.matcher(contentType); /* If Content-Type doesn't match this pre-conception, choose default and hope for the best. */ return m.matches() ? m.group(1) : "ISO-8859-1"; } static Class getClass(String name) { try { return Class.forName(name); } catch (ClassNotFoundException e) { return null; } } static Object call(Object o, String method, Object... args) { try { Method m = call_findMethod(o, method, args, false); m.setAccessible(true); return m.invoke(o, args); } catch (Exception e) { throw new RuntimeException(e); } } static Object call(Class c, String method, Object... args) { try { Method m = call_findStaticMethod(c, method, args, false); m.setAccessible(true); return m.invoke(null, args); } catch (Exception e) { throw new RuntimeException(e); } } static Method call_findStaticMethod(Class c, String method, Object[] args, boolean debug) { while (c != null) { for (Method m : c.getDeclaredMethods()) { if (debug) System.out.println("Checking method " + m.getName() + " with " + m.getParameterTypes().length + " parameters");; if (!m.getName().equals(method)) { if (debug) System.out.println("Method name mismatch: " + method); continue; } if ((m.getModifiers() & Modifier.STATIC) == 0 || !call_checkArgs(m, args, debug)) continue; return m; } c = c.getSuperclass(); } throw new RuntimeException("Method '" + method + "' (static) with " + args.length + " parameter(s) not found in " + c.getName()); } static Method call_findMethod(Object o, String method, Object[] args, boolean debug) { Class c = o.getClass(); while (c != null) { for (Method m : c.getDeclaredMethods()) { if (debug) System.out.println("Checking method " + m.getName() + " with " + m.getParameterTypes().length + " parameters");; if (m.getName().equals(method) && call_checkArgs(m, args, debug)) return m; } c = c.getSuperclass(); } throw new RuntimeException("Method '" + method + "' (non-static) with " + args.length + " parameter(s) not found in " + o.getClass().getName()); } private static boolean call_checkArgs(Method m, Object[] args, boolean debug) { Class[] types = m.getParameterTypes(); if (types.length != args.length) { if (debug) System.out.println("Bad parameter length: " + args.length + " vs " + types.length); return false; } for (int i = 0; i < types.length; i++) if (!(args[i] == null || types[i].isInstance(args[i]))) { if (debug) System.out.println("Bad parameter " + i + ": " + args[i] + " vs " + types[i]); return false; } return true; } static String patternQuote(String s) { return s.length() == 0 ? "" : Pattern.quote(s); } public static String join(String glue, Iterable strings) { StringBuilder buf = new StringBuilder(); Iterator i = strings.iterator(); if (i.hasNext()) { buf.append(i.next()); while (i.hasNext()) buf.append(glue).append(i.next()); } return buf.toString(); } public static String join(String glue, String[] strings) { return join(glue, Arrays.asList(strings)); } static String unnull(String s) { return s == null ? "" : s; } } class JavaTok { static String join(List cnc) { StringBuilder buf = new StringBuilder(); for (String s : cnc) buf.append(s); return buf.toString(); } static List split(String src) { Java20 lex = new Java20(); src = src.replace("\r\n", "\n"); LineNumberReader source = new LineNumberReader(new StringReader(src)); int lineNr = source.getLineNumber()+1; List list = new ArrayList(); try { for (Object a; (a = lex.grab(source)) != lex.$;) { String word = lex.word(); String q = quote(word); //System.out.println("grabbed at line " + lineNr + ": " + a + " " + q); lineNr = source.getLineNumber()+1; T t = new T(a, word); boolean isSpace = t.isSpace(); if (isSpace && list.size() > 0 && list.get(list.size()-1).isSpace()) list.get(list.size()-1).word += word; // merge spaces else list.add(t); } } catch (Lexicon.Exception e) { throw new RuntimeException(e); } List cnc = new ArrayList(); for (int i = 0; i < list.size(); ) { T t = list.get(i); boolean shouldBeSpace = (cnc.size() % 2) == 0; boolean isSpace = t.isSpace(); if (shouldBeSpace == isSpace) { cnc.add(t.word); ++i; } else if (shouldBeSpace) cnc.add(""); else { System.out.println(cncToLines(cnc)); throw new RuntimeException("TILT at " + cnc.size() + ": " + quote(t.word)); } } if ((cnc.size() % 2) == 0) cnc.add(""); return cnc; } static class T { Object a; String word; T(Object a, String word) { this.a = a; this.word = word; } boolean isSpace() { return a.equals("WHITE_SPACE") || a.equals("COMMENT"); } } static String cncToLines(List cnc) { StringBuilder out = new StringBuilder(); for (String token : cnc) out.append(quote(token) + "\n"); return out.toString(); } public static String quote(String s) { if (s == null) return "null"; return "\"" + s.replace("\\", "\\\\").replace("\"", "\\\"").replace("\r", "\\r").replace("\n", "\\n") + "\""; } static class Java20 extends Lexicon { Java20() { /** * Grammar for Java 2.0. * * Nonterminal - first letter uppercase * TERMINAL - all letters uppercase * keyword - all letters lowercase */ int INFINITY = -1; /** * 19.3 Terminals from section 3.6: White Space: [[:space:]] */ put("WHITE_SPACE", new Repetition(PosixClass.space(), 1, INFINITY)); /** * 19.3 Terminals from section 3.7: Comment */ put("COMMENT", new Union( // // Traditional Comment: /\*[^*]+(\*([^*/][^*]*)?)*\*/ // new Concatenation( new Singleton("/*"), new Concatenation( new Repetition(new NonMatch("*"), 1, INFINITY), new Concatenation( new Repetition( new Concatenation( new Singleton("*"), new Repetition(new Concatenation( new NonMatch("*/"), new Repetition(new NonMatch("*"), 0, INFINITY) ), 0, 1) ), 0, INFINITY ), new Singleton("*/") ))), new Union( /** * End Of Line Comment: //[^\n]*\n */ new Concatenation( new Singleton("//"), new Concatenation( new Repetition(new NonMatch("\n"), 0, INFINITY), new Singleton("\n") )), // // Documentation Comment: /\*\*(([^*/][^*]*)?\*)*/ // new Concatenation( new Singleton("/**"), new Concatenation( new Repetition( new Concatenation( new Repetition(new Concatenation( new NonMatch("*/"), new Repetition(new NonMatch("*"), 0, INFINITY) ), 0, 1), new Singleton("*") ), 0, INFINITY ), new Singleton("/") )) ))); put("IDENTIFIER", new Concatenation( new Union( PosixClass.alpha(), new Match("_$") ), new Repetition( new Union( PosixClass.alnum(), new Match("_$") ), 0, INFINITY ) )); /** * 19.3 Terminals from section 3.9: Keyword (recognized but not in the Java grammar) */ put("KEYWORD", new Union( new Singleton("const"), new Singleton("goto") )); /** * 19.3 Terminals from section 3.10.1: Integer Literal */ put("INTEGER_LITERAL", new Concatenation( new Union( /** * Decimal Integer Literal: 0|[1-9][[:digit:]]* */ new Singleton("0"), new Union( new Concatenation( new Range('1', '9'), new Repetition(PosixClass.digit(), 0, INFINITY) ), new Union( /** * Hexadecimal Integer Literal: 0[xX][[:xdigit:]]+ */ new Concatenation( new Singleton("0"), new Concatenation( new Match("xX"), new Repetition(PosixClass.xdigit(), 1, INFINITY) )), /** * Octal Integer Literal: 0[0-7]+ */ new Concatenation( new Singleton("0"), new Repetition(new Range('0', '7'), 1, INFINITY) ) ))), new Repetition(new Match("lL"), 0, 1) )); /** * 19.3 Terminals from section 3.10.2: Floating-Point Literal */ put("FLOATING_POINT_LITERAL", new Union( /** * [[:digit:]]+\.[[:digit:]]*([eE][-+]?[[:digit:]]+)?[fFdD]? */ new Concatenation( new Repetition(PosixClass.digit(), 1, INFINITY), new Concatenation( new Singleton("."), new Concatenation( new Repetition(PosixClass.digit(), 0, INFINITY), new Concatenation( new Repetition(new Concatenation( new Match("eE"), new Concatenation( new Repetition(new Match("-+"), 0, 1), new Repetition(PosixClass.digit(), 1, INFINITY) )), 0, 1), new Repetition(new Match("fFdD"), 0, 1) )))), new Union( /** * \.[[:digit:]]+([eE][-+]?[[:digit:]]+)?[fFdD]? */ new Concatenation( new Singleton("."), new Concatenation( new Repetition(PosixClass.digit(), 1, INFINITY), new Concatenation( new Repetition(new Concatenation( new Match("eE"), new Concatenation( new Repetition(new Match("-+"), 0, 1), new Repetition(PosixClass.digit(), 1, INFINITY) )), 0, 1), new Repetition(new Match("fFdD"), 0, 1) ))), new Union( /** * [[:digit:]]+[eE][-+]?[[:digit:]]+[fFdD]? */ new Concatenation( new Repetition(PosixClass.digit(), 1, INFINITY), new Concatenation( new Match("eE"), new Concatenation( new Repetition(new Match("-+"), 0, 1), new Concatenation( new Repetition(PosixClass.digit(), 1, INFINITY), new Repetition(new Match("fFdD"), 0, 1) )))), /** * [[:digit:]]+([eE][-+]?[[:digit:]]+)?[fFdD] */ new Concatenation( new Repetition(PosixClass.digit(), 1, INFINITY), new Concatenation( new Repetition(new Concatenation( new Match("eE"), new Concatenation( new Repetition(new Match("-+"), 0, 1), new Repetition(PosixClass.digit(), 1, INFINITY) )), 0, 1), new Match("fFdD") )) )))); /** * 19.3 Terminals from section 3.10.3: Boolean Literal */ put("BOOLEAN_LITERAL", new Union( new Singleton("true"), new Singleton("false") )); /** * 19.3 Terminals from section 3.10.4: Character Literal */ put("CHARACTER_LITERAL", new Concatenation( new Singleton("'"), new Concatenation( new Union( /** * Single Character: [^\r\n'\\] */ new NonMatch("\r\n'\\"), /** * Escape Sequence: \\([btnfr\"'\\]|[0-3]?[0-7]{1,2}) */ new Concatenation( new Singleton("\\"), new Union( new Match("btnfr\"'\\"), new Concatenation( new Repetition(new Range('0', '3'), 0, 1), new Repetition(new Range('0', '7'), 1, 2) ) ) ) ), new Singleton("'") ))); put("MULTILINE_LITERAL", new Concatenation( new Singleton("[["), new Concatenation( new Repetition( new Union( new NonMatch("]"), new Concatenation( new Singleton("]"), new NonMatch("]")) ), 0, INFINITY ), new Singleton("]]") ))); /** * 19.3 Terminals from section 3.10.5: String Literal */ put("STRING_LITERAL", new Concatenation( new Singleton("\""), new Concatenation( new Repetition( new Union( /** * Single Character: [^\r\n"\\] */ new NonMatch("\r\n\"\\"), /** * Escape Sequence: \\([btnfr\"'\\]|[0-3]?[0-7]{1,2}) */ new Concatenation( new Singleton("\\"), new Union( new Match("btnfr\"'\\"), new Union( new Concatenation( new Repetition(new Range('0', '3'), 0, 1), new Repetition(new Range('0', '7'), 1, 2) ), new Concatenation( new Singleton("u"), new Repetition(new Match("0123456789abcdefABCDEF"), 4, 4) ) ) ) ) ), 0, INFINITY ), new Singleton("\"") ))); /** * 19.3 Terminals section 3.10.7: Null Literal */ put("NULL_LITERAL", new Singleton("null")); // OK, it seems we have to add some more stuff... //put("OTHER1", new Match(";{}=,<>[]().+-:|&!")); //put("OTHER1", new NonMatch("")); // catch anything, one character at a time put("OTHER1", new NonMatch(" \t\r\n")); // catch any non-whitespace, one character at a time } } // class Java20 } /** *

This class implements a {@link Lexicon}.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ class Lexicon { //Q /** *

The number of lexical NFA states constructed.

*/ private static int QSize = 0; /** *

Creates a new state in the lexical NFA.

* * @return a new state in the lexical NFA. */ private static Integer s() { return ++QSize; } //delta /** *

The transition relation of the lexical NFA.

*/ private static final Stack> delta = new Stack>(); /** *

Puts a transition into the lexical NFA.

* * @param s the state from which the transition is made. * @param A the Alphabet on which the transition is made. * @param r the state to which the transition is made. */ private static void put(Integer s, Alphabet A, Integer r) { if (Math.max(s,r) >= delta.size()) delta.setSize(Math.max(s,r)+1); Stack pairs = delta.get(s); if (pairs == null) delta.set(s, pairs = new Stack()); pairs.push(A); pairs.push(r); } //Set /** *

This class implements a {@link Lexicon.Set Set}.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> * @param the element type. */ static class Set extends Stack { /** *

The null exclusion indicator. If true, add methods will not add null to this Set.

*/ private final boolean excludeNull; /** *

Constructs a Set with an initial capacity.

* * @param capacity the initial capacity. The magnitude of capacity is the initial capacity. The null exclusion indicator is initialized to true if capacity is negative. */ Set(int capacity) { super(); ensureCapacity(Math.abs(capacity)); excludeNull = (capacity < 0); } /** *

Adds an element to this Set. The element is not added if it occurs in this Set or it is null and the null exclusion indicator is true. The capacity is expanded if necessary.

* * @param element the element to add to this Set. * @return true if this Set is changed; false otherwise. */ public boolean add(E element) { if (excludeNull && element == null || contains(element)) return false; push(element); return true; } /** *

Adds a Set of elements to this Set. An element is not added if it occurs in this Set or it is null and the null exclusion indicator is true. The capacity is expanded if necessary.

* * @param index the index in S beyond which elements are added. * @param S the Set to add to this Set. * @return true if this Set is changed; false otherwise. */ boolean add(int index, Set S) { if (S == null) return false; boolean push = isEmpty(); boolean add = false; for (int i = index; i < S.size(); i++) { E element = S.get(i); if (!(excludeNull && element == null)) if (push) { push(element); add = true; } else if (add(element)) add = true; } return add; } /** *

Adds a Set of elements to this Set. An element is not added if it occurs in this Set or it is null and the null exclusion indicator is true. The capacity is expanded if necessary.

* * @param S the Set to add to this Set. * @return true if this Set is changed; false otherwise. */ boolean add(Set S) { return add(0, S); } public String toString() { StringBuffer result = new StringBuffer(80); result.append('{'); for (int i = 0; i < size(); i++) { if (i > 0) result.append(' '); result.append(get(i)); } result.append('}'); return result.toString(); } //Set } //I /** *

The initial states of the lexical NFA. When empty, there is a need to compute the current initial states. It is computed only on demand created by {@link #initial()}.

*/ private final Set I; //F /** *

The final states of the lexical NFA. A final state is mapped to the terminal it accepts in this Lexicon. When empty, there is a need to compute current final states. It is computed only on demand created by {@link #initial()}.

*/ private final Map F; //Lexicon.transition /** *

Computes a transition using the lexical NFA.

* * @param S the states from which the transition is made. * @param a the character on which the transition is made. * @param R the states to which the transition is made. * @return the states to which the transition is made. */ private static Set transition(Set S, char a, Set R) { R.clear(); for (Integer s : S) { Stack pairs = delta.get(s); if (pairs != null) for (int k = 0; k < pairs.size(); k += 2) { Alphabet A = (Alphabet)pairs.get(k); if (A != null) { Integer r = (Integer)pairs.get(k+1); if (A.contains(a)) R.add(r); } } } return R; } //Lexicon.closure /** *

Computes a reflexive transitive closure under empty transition using the lexical NFA. The closure is computed in place by a breadth-first search expanding S.

* * @param S the states whose reflexive transitive closure is computed under empty transition. * @return the reflexive transitive closure of S under empty transition. */ private static Set closure(Set S) { for (int i = 0; i < S.size(); i++) { Integer s = S.get(i); Stack pairs = delta.get(s); if (pairs != null) for (int k = 0; k < pairs.size(); k += 2) { Alphabet A = (Alphabet)pairs.get(k); if (A == null) { Integer r = (Integer)pairs.get(k+1); S.add(r); } } } return S; } //Expression /** *

This class implements an {@link Lexicon.Expression Expression} expressing a regular language.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ abstract public static class Expression implements Cloneable { /** *

The initial state of the NFA constructed from this Expression.

*/ Integer i; /** *

The final state of the NFA constructed from this Expression.

*/ Integer f; /** *

Creates a clone of this Expression, and replicates the NFA constructed from this Expression.

* * @return a clone of this Expression. */ abstract public Object clone(); } //Alphabet /** *

This class implements an {@link Lexicon.Alphabet Alphabet} of character symbols.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ abstract public static class Alphabet extends Expression { /** *

Indicates whether a character occurs in this Alphabet.

* * @param a the character whose status is requested. * @return true if a occurs in this Alphabet; false otherwise. */ abstract boolean contains(char a); } //Match /** *

This class implements an {@link Lexicon.Alphabet Alphabet} containing some characters.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ public static class Match extends Alphabet { /** *

The {@link Character} or {@link String} representing this Alphabet.

*/ final Object A; /** *

Constructs an Alphabet containing some characters, and builds the NFA constructed from this Expression.

* * @param i the initial state of the NFA constructed. * @param A the {@link Character} or {@link String} of characters in this Alphabet. * @param f the final state of the NFA constructed. */ private Match(Integer i, Object A, Integer f) { this.A = A; put(this.i = i, this, this.f = f); } /** *

Constructs an Alphabet containing one character, and builds the NFA constructed from this Expression.

* * @param i the initial state of the NFA constructed. * @param a the character in this Alphabet. * @param f the final state of the NFA constructed. */ private Match(Integer i, char a, Integer f) { this(i, new Character(a), f); } /** *

Constructs an Alphabet containing one character, and builds the NFA constructed from this Expression.

* * @param a the character in this Alphabet. */ public Match(char a) { this(s(), a, s()); } /** *

Constructs an Alphabet containing some characters, and builds the NFA constructed from this Expression.

* * @param A the {@link Character} or {@link String} of characters in this Alphabet. */ public Match(Object A) { this(s(), A, s()); } /** *

Indicates whether a character occurs in this Alphabet.

* * @param a the character whose status is requested. * @return true if a occurs in this Alphabet; false otherwise. */ boolean contains(char a) { if (A instanceof Character) return (Character)A == a; if (A instanceof String) return ((String)A).indexOf(a) != -1; if (A instanceof Stack) for (Alphabet alphabet : (Stack)A) if (alphabet.contains(a)) return true; return false; } /** *

Creates a clone of this Alphabet, and replicates the NFA constructed from this Expression.

* * @return a clone of this Alphabet. */ public Object clone() { return new Match(A); } } //NonMatch /** *

This class implements an {@link Lexicon.Alphabet Alphabet} containing all except some characters.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ public static class NonMatch extends Match { /** *

Constructs an Alphabet containing all characters except one, and builds the NFA constructed from this Expression.

* * @param a the character not in this Alphabet. */ public NonMatch(char a) { super(a); } /** *

Constructs an Alphabet containing all characters except some, and builds the NFA constructed from this Expression.

* * @param A the {@link Character} or {@link String} of characters not in this Alphabet. */ public NonMatch(Object A) { super(A); } /** *

Indicates whether a character occurs in this Alphabet.

* * @param a the character whose status is requested. * @return true if a occurs in this Alphabet; false otherwise. */ boolean contains(char a) { return a != (char)-1 && !super.contains(a); } /** *

Creates a clone of this Alphabet, and replicates the NFA constructed from this Expression.

* * @return a clone of this Alphabet. */ public Object clone() { return new NonMatch(A); } } //Range /** *

This class implements an {@link Lexicon.Alphabet Alphabet} containing the characters in a range.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ public static class Range extends Alphabet { /** *

The first character in the range.

*/ private final char a1; /** *

The last character in the range.

*/ private final char a2; /** *

Constructs an Alphabet containing the characters in a range, and builds the NFA constructed from this Expression.

* * @param a1 the first character in the range. * @param a2 the last character in the range. */ public Range(char a1, char a2) { this.a1 = a1; this.a2 = a2; put(i = s(), this, f = s()); } /** *

Indicates whether a character occurs in this Alphabet.

* * @param a the character whose status is requested. * @return true if a occurs in this Alphabet; false otherwise. */ boolean contains(char a) { return a1 <= a && a <= a2; } /** *

Creates a clone of this Alphabet, and replicates the NFA constructed from this Expression.

* * @return a clone of this Alphabet. */ public Object clone() { return new Range(a1, a2); } } /** *

This class implements an {@link Lexicon.Alphabet Alphabet} containing the characters in a POSIX character class.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ public static class PosixClass extends Alphabet { /** *

The bit mask representing this PosixClass.

*/ private final int posixClass; /** *

Constructs an Alphabet containing the characters in a POSIX character class, and builds the NFA constructed from this Expression.

* * @param posixClass the bit mask representing this PosixClass. */ private PosixClass(int posixClass) { this.posixClass = posixClass; put(i = s(), this, f = s()); } /** *

Creates an Alphabet containing the uppercase alphabetic characters.

* * @return an Alphabet containing the uppercase alphabetic characters. */ public static PosixClass upper() { return new PosixClass(0x0001); } /** *

Creates an Alphabet containing the lowercase alphabetic characters.

* * @return an Alphabet containing the lowercase alphabetic characters. */ public static PosixClass lower() { return new PosixClass(0x0002); } /** *

Creates an Alphabet containing the alphabetic characters.

* * @return an Alphabet containing the alphabetic characters. */ public static PosixClass alpha() { return new PosixClass(0x0004); } /** *

Creates an Alphabet containing the decimal digit characters.

* * @return an Alphabet containing the decimal digit characters. */ public static PosixClass digit() { return new PosixClass(0x0008); } /** *

Creates an Alphabet containing the hexadecimal digit characters.

* * @return an Alphabet containing the hexadecimal digit characters. */ public static PosixClass xdigit() { return new PosixClass(0x0010); } /** *

Creates an Alphabet containing the alphanumeric characters.

* * @return an Alphabet containing the alphanumeric characters. */ public static PosixClass alnum() { return new PosixClass(0x0020); } /** *

Creates an Alphabet containing the punctuation characters.

* * @return an Alphabet containing the punctuation characters. */ public static PosixClass punct() { return new PosixClass(0x0040); } /** *

Creates an Alphabet containing the graphical characters.

* * @return an Alphabet containing the graphical characters. */ public static PosixClass graph() { return new PosixClass(0x0080); } /** *

Creates an Alphabet containing the printable characters.

* * @return an Alphabet containing the printable characters. */ public static PosixClass print() { return new PosixClass(0x0100); } /** *

Creates an Alphabet containing the blank characters.

* * @return an Alphabet containing the blank characters. */ public static PosixClass blank() { return new PosixClass(0x0200); } /** *

Creates an Alphabet containing the space characters.

* * @return an Alphabet containing the space characters. */ public static PosixClass space() { return new PosixClass(0x0400); } /** *

Creates an Alphabet containing the control characters.

* * @return an Alphabet containing the control characters. */ public static PosixClass cntrl() { return new PosixClass(0x0800); } /** *

Indicates whether a character occurs in this Alphabet.

* * @param a the character whose status is requested. * @return true if a occurs in this Alphabet; false otherwise. */ boolean contains(char a) { int UPPER = 0x0001; int LOWER = 0x0002; int ALPHA = 0x0004; int DIGIT = 0x0008; int XDIGIT = 0x0010; int ALNUM = 0x0020; int PUNCT = 0x0040; int GRAPH = 0x0080; int PRINT = 0x0100; int BLANK = 0x0200; int SPACE = 0x0400; int CNTRL = 0x0800; int classes = 0; switch (Character.getType(a)) { default: break; case Character.UPPERCASE_LETTER: classes |= UPPER | ALPHA | (('A' <= a && a <= 'F') ? XDIGIT : 0) | ALNUM | GRAPH | PRINT; break; case Character.LOWERCASE_LETTER: classes |= LOWER | ALPHA | (('a' <= a && a <= 'f') ? XDIGIT : 0) | ALNUM | GRAPH | PRINT; break; case Character.TITLECASE_LETTER: case Character.MODIFIER_LETTER: case Character.OTHER_LETTER: classes |= ALPHA | ALNUM | GRAPH | PRINT; break; case Character.NON_SPACING_MARK: case Character.COMBINING_SPACING_MARK: case Character.ENCLOSING_MARK: classes |= PUNCT | GRAPH | PRINT; break; case Character.DECIMAL_DIGIT_NUMBER: classes |= DIGIT | XDIGIT | ALNUM | GRAPH | PRINT; break; case Character.LETTER_NUMBER: case Character.OTHER_NUMBER: classes |= ALNUM | GRAPH | PRINT; break; case Character.CONNECTOR_PUNCTUATION: case Character.DASH_PUNCTUATION: case Character.START_PUNCTUATION: case Character.END_PUNCTUATION: case Character.INITIAL_QUOTE_PUNCTUATION: case Character.FINAL_QUOTE_PUNCTUATION: case Character.OTHER_PUNCTUATION: case Character.MATH_SYMBOL: case Character.CURRENCY_SYMBOL: case Character.MODIFIER_SYMBOL: case Character.OTHER_SYMBOL: classes |= PUNCT | GRAPH | PRINT; break; case Character.SPACE_SEPARATOR: classes |= PRINT | BLANK | SPACE; break; case Character.LINE_SEPARATOR: case Character.PARAGRAPH_SEPARATOR: break; case Character.CONTROL: classes |= ((a == '\t') ? BLANK : 0) | ((a == '\t' || a == '\n' || a == '\013' || a == '\f' || a == '\r') ? SPACE : 0) | CNTRL; break; case Character.FORMAT: case Character.SURROGATE: case Character.PRIVATE_USE: case Character.UNASSIGNED: break; } return (classes & posixClass) != 0; } /** *

Creates a clone of this Alphabet, and replicates the NFA constructed from this Expression.

* * @return a clone of this Alphabet. */ public Object clone() { return new PosixClass(posixClass); } } //UnicodeCategory /** *

This class implements an {@link Lexicon.Alphabet Alphabet} containing the characters in a Unicode general category.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ public static class UnicodeCategory extends Alphabet { /** *

The byte representing the Unicode general category.

*/ private final byte category; /** *

Constructs an Alphabet containing the characters in a Unicode general category, and builds the NFA constructed from this Expression. The class {@link Character} defines byte constants representing each of the Unicode general categories.

* * @param category The byte representing the Unicode general category. * @see Character */ public UnicodeCategory(byte category) { this.category = category; put(i = s(), this, f = s()); } /** *

Indicates whether a character occurs in this Alphabet.

* * @param a the character whose status is requested. * @return true if a occurs in this Alphabet; false otherwise. */ boolean contains(char a) { return Character.getType(a) == category; } /** *

Creates a clone of this Alphabet, and replicates the NFA constructed from this Expression.

* * @return a clone of this Alphabet. */ public Object clone() { return new UnicodeCategory(category); } } //Repetition /** *

This class implements an {@link Lexicon.Expression Expression} expressing the repetition of a regular language.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ public static class Repetition extends Expression { /** *

The operand Expression.

*/ private final Expression e1; /** *

The minimum number of times e1 is repeated.

*/ private final int min; /** *

The maximum number of times e1 is repeated.

*/ private final int max; /** *

Constructs an Expression expressing the repetition of a regular language, and builds the NFA constructed from this Expression. Large finite values for the minimum or maximum cause the NFA constructed from the operand Expression to be copied many times, resulting in a space-inefficient NFA.

* * @param e1 the operand Expression. * @param min the minimum number of times e1 is repeated. If negative, it is assumed to be zero. * @param max the maximum number of times e1 is repeated. If negative, it is assumed to be infinity. */ public Repetition(Expression e1, int min, int max) { this.e1 = e1 = (Expression)e1.clone(); this.min = min = Math.max(min, 0); this.max = max; i = (min > 0) ? e1.i : s(); f = (min > 0) ? e1.f : i; if (min == 0 && max < 0) { put(i, null, e1.i); put(e1.f, null, i); } else { for (int k = 2; k <= min; k++) { e1 = (Expression)e1.clone(); put(f, null, e1.i); f = e1.f; } if (max > min) { Integer tail = f; put(tail, null, f = s()); for (int k = min+1; k <= max; k++) { if (k > 1) e1 = (Expression)e1.clone(); put(tail, null, e1.i); put(tail = e1.f, null, f); } } else if (max < 0) put(f, null, e1.i); } } /** *

Creates a clone of this Expression, and replicates the NFA constructed from this Expression.

* * @return a clone of this Expression. */ public Object clone() { return new Repetition(e1, min, max); } } //Concatenation /** *

This class implements an {@link Lexicon.Expression Expression} expressing the concatenation of two regular languages.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ public static class Concatenation extends Expression { /** *

The left operand Expression.

*/ private final Expression e1; /** *

The right operand Expression.

*/ private final Expression e2; /** *

Constructs an Expression expressing the concatenation of two regular languages, and builds the NFA constructed from this Expression.

* * @param e1 the left operand Expression. * @param e2 the right operand Expression. */ public Concatenation(Expression e1, Expression e2) { this.e1 = e1 = (Expression)e1.clone(); this.e2 = e2 = (Expression)e2.clone(); i = e1.i; f = e2.f; put(e1.f, null, e2.i); } /** *

Creates a clone of this Expression, and replicates the NFA constructed from this Expression.

* * @return a clone of this Expression. */ public Object clone() { return new Concatenation(e1, e2); } } //Singleton /** *

This class implements an {@link Lexicon.Expression Expression} expressing a singleton language.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ public static class Singleton extends Expression { /** *

The string whose singleton language is expressed.

*/ private final String x; /** *

Constructs an Expression expressing a singleton language, and builds the NFA constructed from this Expression.

* * @param x the string whose singleton language is expressed. */ public Singleton(String x) { this.x = x; f = i = s(); for (char c : x.toCharArray()) new Match(f, c, f = s()); } /** *

Creates a clone of this Expression, and replicates the NFA constructed from this Expression.

* * @return a clone of this Expression. */ public Object clone() { return new Singleton(x); } } //Union /** *

This class implements an {@link Lexicon.Expression Expression} expressing the union of two regular languages.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ public static class Union extends Expression { /** *

The left operand Expression.

*/ private final Expression e1; /** *

The right operand Expression.

*/ private final Expression e2; /** *

Constructs an Expression expressing the union of two regular languages, and builds the NFA constructed from this Expression.

* * @param e1 the left operand Expression. * @param e2 the right operand Expression. */ public Union(Expression e1, Expression e2) { this.e1 = e1 = (Expression)e1.clone(); this.e2 = e2 = (Expression)e2.clone(); i = s(); f = s(); put(i, null, e1.i); put(e1.f, null, f); put(i, null, e2.i); put(e2.f, null, f); } /** *

Creates a clone of this Expression, and replicates the NFA constructed from this Expression.

* * @return a clone of this Expression. */ public Object clone() { return new Union(e1, e2); } } /** *

The mapping representing this Lexicon. A terminal is mapped to the initial state of the NFA constructed from the associated Expression.

*/ private final Map E; /** *

Puts a terminal and associated Expression into this Lexicon. The Expression supersedes any previously associated with the terminal.

* * @param a the terminal to add to this Lexicon. * @param e the Expression associated with terminal a. When grabbing, the language expressed by e matches a. */ public void put(Object a, Expression e) { E.put(a, e); I.clear(); F.clear(); } /** *

Indicates whether a symbol is a terminal in this Lexicon.

* * @param a the symbol whose status is requested. * @return true if a is a terminal in this Lexicon; false otherwise. */ boolean terminal(Object a) { return E.containsKey(a); } //Lexicon() /** *

The terminal matched by the character at the end of a source stream.

* @since 1.1, renames END_OF_SOURCE in version 1.0. */ protected static final Object $ = new String("$"); /** *

The Alphabet containing the character at the end of a source stream.

*/ private static final Expression $_EXPRESSION = new Match((char)-1); /** *

Constructs an empty Lexicon.

*/ protected Lexicon() { E = new HashMap(500); I = new Set(-200); F = new HashMap(500); put($, $_EXPRESSION); } /** *

Constructs a Lexicon that is a shallow copy of lexicon. The fields of the new Lexicon refer to the same elements as those in lexicon.

* * * @param lexicon the Lexicon to copy. */ Lexicon(Lexicon lexicon) {/*debug*/ debug = lexicon.debug;/*off*/ E = lexicon.E; I = lexicon.I; F = lexicon.F; } //Lexicon.initial /** *

Returns the initial states of the lexical NFA.

* * @return {@link #I}, computing it and {@link #F} if there is a need to compute the current initial states and final states. */ private Set initial() { if (I.isEmpty()) { for (Object a : E.keySet()) { Expression e = E.get(a); I.add(e.i); F.put(e.f, a); } closure(I); } return I; } //accept /** *

Computes the current final state, if any, in the lexical NFA.

* * @param S the current states. * @return the maximum final state in S. Returns null if S contains no final states. */ private Integer accept(Set S) { Integer f = null; for (Integer s : S) if (F.containsKey(s)) if (f == null || f < s) f = s; return f; } /** *

This class implements an {@link Lexicon.Exception Exception}.

* * @version 1.3 * @author © 1999-2009 Craig A. Rich <carich@csupomona.edu> */ public class Exception extends java.lang.Exception { /** *

The extended error message.

*/ private StringBuffer message; /** *

Constructs an Exception with a message.

* * @param message the error message. */ public Exception(String message) { super(message); } /** *

Returns the error message.

* * @return the error message. */ public String getMessage() { return (message == null) ? super.getMessage() : message.toString(); } /** *

Extends the error message in this Exception. The extended message includes the line number, message and source characters following the error.

* * @param source the source character stream. * @return this Exception with an extended message. */ Exception extend(LineNumberReader source) { if (message == null) message = new StringBuffer(132); else message.setLength(0); message.append("line "); message.append(source.getLineNumber()+1); message.append(": "); message.append(super.getMessage()); message.append(System.getProperty("line.separator")); message.append("..."); message.append(word()); try { String rest = source.readLine(); if (rest != null) message.append(rest); } catch (IOException exception) {} message.append(System.getProperty("line.separator")); message.append(" ^"); return this; } } //Lexicon.grab /** *

The states through which the lexical NFA transitions.

*/ private final Set[] R = (Set[])new Set[]{new Set(-200), new Set(-200)}; /** *

The StringBuffer containing the word most recently grabbed.

*/ private final StringBuffer w = new StringBuffer(4000); /** *

Grabs a terminal from a source character stream using this Lexicon. The variable returned by {@link #word()} is set to the longest nonempty prefix of the remaining source characters matching an Expression in this Lexicon. If no nonempty prefix matches an Expression, a Lexicon.Exception is thrown. If the longest matching prefix matches more than one Expression, the terminal associated with the Expression most recently constructed is returned. Blocks until a character is available, an I/O error occurs, or the end of the source stream is reached.

* * @param source the source character stream. * @return the terminal grabbed from source. * @throws Lexicon.Exception if an I/O or lexical error occurs. */ protected Object grab(LineNumberReader source) throws Exception { Set S = initial(); w.setLength(0); int wLength = 0; Object b = null; try { source.mark(w.capacity()); do { int a = source.read(); S = closure(transition(S, (char)a, R[w.length() % 2])); if (S.isEmpty()) break; if (a != -1) w.append((char)a); else w.append($); Integer f = accept(S); if (f != null) { wLength = w.length(); b = F.get(f); source.mark(w.capacity()); } } while (b != $); w.setLength(wLength); source.reset(); } catch (IOException exception) { throw new Exception(exception.getMessage()); } if (wLength == 0) throw new Exception("lexical error").extend(source); return b; } /** *

Returns the word most recently grabbed using this Lexicon.

* * @return the word most recently grabbed by {@link #grab(java.io.LineNumberReader) grab(source)}. */ protected String word() { return w.substring(0); } //Lexicon.interpret /** *

Repeatedly invokes {@link #grab(java.io.LineNumberReader) grab(source)} until the end of the source stream reached. Blocks until a character is available, or an I/O error occurs. This method is overridden by Grammar and its parser subclasses, so it is only invoked when this Lexicon has not been extended into a Grammar or parser.

* * @param source the source character stream. * @return the ParseTree constructed by interpreting source. A Lexicon always returns null. * @throws Lexicon.Exception if an I/O or lexical error occurs. */ Object interpret(LineNumberReader source) throws Exception {/*debug*/ if ((debug & TERMINALS) > 0) System.out.println( "----terminals\n\t" + E.keySet().toString().replaceFirst("\\[", "{").replaceAll(", ", " ").replaceFirst("\\]$", "}\n----------"));/*off*/ for (Object a; (a = grab(source)) != $;)/*debug*/ if ((debug & LEXICAL) > 0) System.out.println( a + (!a.equals(word()) ? " " + word() : ""))/*off*/ ; return null; } /** *

Interprets a source character stream using this Lexicon.

* * @param source the source character stream. * @return the ParseTree constructed by interpreting source. * @throws Lexicon.Exception if an I/O, lexical, syntax or semantic error occurs. */ public Object interpret(Reader source) throws Exception { return interpret(new LineNumberReader(source)); } /** *

Interprets a source string using this Lexicon.

* * @param source the source string. * @return the ParseTree constructed by interpreting source. * @throws Lexicon.Exception if an I/O, lexical, syntax or semantic error occurs. */ public Object interpret(String source) throws Exception { return interpret(new StringReader(source)); } /** *

Interprets a source byte stream using this Lexicon.

* * @param source the source byte stream. * @return the ParseTree constructed by interpreting source. * @throws Lexicon.Exception if an I/O, lexical, syntax or semantic error occurs. */ public Object interpret(InputStream source) throws Exception { return interpret(new InputStreamReader(source)); } /** *

Interprets the standard input stream using this Lexicon.

* * @return the ParseTree constructed by interpreting the standard input stream. * @throws Lexicon.Exception if an I/O, lexical, syntax or semantic error occurs. */ public Object interpret() throws Exception { return interpret(System.in); } /** *

Interprets a source file using this Lexicon.

* * @param source the source file. * @return the ParseTree constructed by interpreting source. * @throws FileNotFoundException if the source file cannot be found. * @throws Lexicon.Exception if an I/O, lexical, syntax or semantic error occurs. */ public Object interpret(File source) throws FileNotFoundException, Exception { return interpret(new FileReader(source)); } /** *

Interprets a source pipe using this Lexicon.

* * @param source the source pipe. * @return the ParseTree constructed by interpreting source. * @throws IOException if the source pipe cannot be connected. * @throws Lexicon.Exception if an I/O, lexical, syntax or semantic error occurs. */ public Object interpret(PipedWriter source) throws IOException, Exception { return interpret(new PipedReader(source)); } //Lexicon.interpret(arguments) /** *

The debug switches, initially zero. The following bits enable debugging to standard output:

*
*
0x01 = TERMINALS
*
Print the set of terminals before lexical analysis
*
0x02 = LEXICAL
*
Print terminals and associated words grabbed during lexical analysis
*
0x04 = FIRST_FOLLOW
*
Print first and follow sets precomputed during syntax analysis
*
0x08 = SYNTAX
*
Print parsing decisions made during syntax analysis
*
0x10 = CONFLICT
*
Print parsing conflicts encountered during syntax analysis
*
0x20 = PARSE_TREE
*
Print each ParseTree produced by syntax analysis
*
* @since 1.1 */ protected int debug = 0; /** *

{@link #debug debug} switch constant enabling printing the set of terminals before lexical analysis.

* @since 1.1 */ protected static final int TERMINALS = 0x01; /** *

{@link #debug debug} switch constant enabling printing terminals and associated words grabbed during lexical analysis.

* @since 1.1 */ protected static final int LEXICAL = 0x02; /** *

{@link #debug debug} switch constant enabling all debugging.

* @since 1.1 */ protected static final int VERBOSE = 0xFF; }