import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.PrintStream;
import java.util.Hashtable;
import java.util.Vector;
import java.util.Enumeration;
import java.lang.Character;

/**
 * 命令の定義ファイルの解析、命令パターンの検索
 */

public class Pattern {

  /*****************/
  /* PRIVATE FIELD */
  /*****************/
  /* アセンブラ名定義テーブル  */
  private Vector asmVec;
  /* defnameテーブル */
  private Hashtable nameList;
  /* 命令データベース */
  private Hashtable instList;
  /* テンプレート・データベース */
  private Hashtable templateList;

  /* マシン依存メソッド */
  TargetMethod targetMethod;

  /* 定数定義 */
  /*  トップレベル */
  private static Cell defnameCell = List.atom("DEFNAME", true);
  private static Cell definstCell = List.atom("DEFINST", true);
  private static Cell deflangCell = List.atom("DEFLANG", true);
  /*  テンプレート定義 */
  private static Cell deftemplateCell = List.atom("DEFTEMPLATE", true);
  /*  メタ・パターン */
  private static Cell holeCell = List.atom("HOLE");

  /* アセンブラ指定 */
  private int langIndex;

  /* デバッグ */
  private static final int debMode = 0;

  /***************/
  /* INITIALIZER */
  /***************/
  /**
   * 中間形式ファイル(バイナリ形式)読み込み時の事前準備を行う。
   */
  public void cleanUp() {
    asmVec = new Vector();
    nameList = new Hashtable();
    instList = new Hashtable();
    templateList = new Hashtable();
  }

  /**
   * 中間形式ファイル(バイナリ形式)読み込み後の再初期化処理を行う。
   */
  public void init() {
    defnameCell = List.atom("DEFNAME", true);
    definstCell = List.atom("DEFINST", true);
    deflangCell = List.atom("DEFLANG", true);
    deftemplateCell = List.atom("DEFTEMPLATE", true);
    holeCell = List.atom("HOLE");
  }

  /***************/
  /* CONSTRUCTOR */
  /***************/
  /**
   * 指定されたターゲット定義ファイルと変換規則クラスを使ったパターン定義
   * オブジェクトを生成する。
   * @param macroTemplateFile		マクロ・テンプレート定義ファイル名
   * @param targetDescriptionFile	中間形式記述のファイル名
   * @param targetMethodClass		アセンブリ言語変換を行うCPU依存クラス
   */
  public Pattern(String macroTemplateFile, String targetDescriptionFile, String targetMethodClass) {
    /*
      ターゲット依存クラス取得
     */
    try {
      Class tmc = Class.forName(targetMethodClass);
      targetMethod = (TargetMethod)tmc.newInstance();
    } catch(ClassNotFoundException e) {
      Util.abort("Pattern: "+e);
    } catch(IllegalAccessException e) {
      Util.abort("Pattern: "+e);
    } catch(InstantiationException e) {
      Util.abort("Pattern: "+e);
    }
    /*
      初期化
     */
    asmVec = new Vector();
    nameList = new Hashtable();
    instList = new Hashtable();
    Vector vi = new Vector();
    templateList = new Hashtable();
    /*
      中間表現の読み込み
     */
    try {
      /* マクロ・テンプレートの解析 */
      ListReader lr = new ListReader(new BufferedReader(new FileReader(macroTemplateFile)));
      parsePattern(lr);
      /* ターゲット記述ファイルの解析 */
      lr = new ListReader(new BufferedReader(new FileReader(targetDescriptionFile)));
      parsePattern(lr);
    } catch( IOException e ) {
      Util.abort("Pattern: "+e);
    }

    // 中間表現パターン数を数える
    int patterns = 0;
    for ( Enumeration e=instList.keys(); e.hasMoreElements(); ) {
      Integer key = (Integer)e.nextElement();
      Vector v = (Vector)instList.get(key);
      patterns += v.size();
    }
    // 統計情報表示
    System.err.println("Pattern:");
    System.err.println("  "+macroTemplateFile+": "
		       +templateList.size()+" templates");
    System.err.println("  "+targetDescriptionFile+": "
		       +nameList.size()+" names, "
		       +patterns+" patterns, "
		       +asmVec.size()+" languages");
  }

  /**
   * 指定されたターゲット定義ファイルと変換規則クラスを使ったパターン定義
   * オブジェクトを生成する。
   * <p>この形式ではマクロ・テンプレートの定義は中間形式記述ファイルに含まれる。
   * @param targetDescriptionFile	中間形式記述のファイル名
   * @param targetMethodClass		アセンブリ言語変換を行うCPU依存クラス
   */
  public Pattern(String targetDescriptionFile, String targetMethodClass) {
    /*
      ターゲット依存クラス取得
     */
    try {
      Class tmc = Class.forName(targetMethodClass);
      targetMethod = (TargetMethod)tmc.newInstance();
    } catch(ClassNotFoundException e) {
      Util.abort("Pattern: "+e);
    } catch(IllegalAccessException e) {
      Util.abort("Pattern: "+e);
    } catch(InstantiationException e) {
      Util.abort("Pattern: "+e);
    }
    /*
      初期化
     */
    asmVec = new Vector();
    nameList = new Hashtable();
    instList = new Hashtable();
    Vector vi = new Vector();
    templateList = new Hashtable();
    /*
      中間表現の読み込み
     */
    try {
      ListReader lr = new ListReader(new BufferedReader(new FileReader(targetDescriptionFile)));
      parsePattern(lr);
    } catch( IOException e ) {
      Util.abort("Pattern: "+e);
    }

    // 中間表現パターン数を数える
    int patterns = 0;
    for ( Enumeration e=instList.keys(); e.hasMoreElements(); ) {
      Integer key = (Integer)e.nextElement();
      Vector v = (Vector)instList.get(key);
      patterns += v.size();
    }
    // 統計情報表示
    System.err.println("Pattern:");
    System.err.println("  "+targetDescriptionFile+": "
		       +templateList.size()+" templates, "
		       +nameList.size()+" names, "
		       +patterns+" patterns, "
		       +asmVec.size()+" languages");
  }

  /**
   * 指定されたターゲット定義ファイルと変換規則クラスを使ったパターン定義
   * オブジェクトを生成する。
   * <p>この形式ではマクロ・テンプレートの定義は中間形式記述ファイルに含まれる。
   * @param targetMethodClass		アセンブリ言語変換を行うCPU依存クラス
   */
  public Pattern(String targetMethodClass) {
    /*
      ターゲット依存クラス取得
     */
    try {
      Class tmc = Class.forName(targetMethodClass);
      targetMethod = (TargetMethod)tmc.newInstance();
    } catch(ClassNotFoundException e) {
      Util.abort("Pattern: "+e);
    } catch(IllegalAccessException e) {
      Util.abort("Pattern: "+e);
    } catch(InstantiationException e) {
      Util.abort("Pattern: "+e);
    }
    /*
      初期化
     */
    asmVec = new Vector();
    nameList = new Hashtable();
    instList = new Hashtable();
    Vector vi = new Vector();
    templateList = new Hashtable();
  }


  /*****************/
  /* PUBLIC METHOD */
  /*****************/
  /**
   * 中間表現をテキスト(DEFINST)形式でファイルに待避する。
   * @param textFile	ダンプ先ファイル名
   */
  public void dumpPattern(String textFile) throws IOException {
    FileOutputStream ostream = new FileOutputStream(textFile);
    PrintStream pstream = new PrintStream(ostream);

    // (DEFLANG ...)の出力
    pstream.print("(DEFLANG ");
    for ( int i=0; i<asmVec.size(); i++ ) {
      pstream.print(((Cell)asmVec.get(i)).toString());
      if ( i!=asmVec.size()-1 )
	pstream.print(" ");
    }
    pstream.println(")");

    // (DEFNAME ...)の出力
    for ( Enumeration e=nameList.keys(); e.hasMoreElements(); ) {
      Cell key = (Cell)e.nextElement();
      pstream.println("(DEFNAME "+key);
      pstream.println(" "+(Cell)nameList.get(key));
      pstream.println(")");
    }

    //    // (DEFTEMPLATE ...)の出力
    //    for ( Enumeration e=templateList.keys(); e.hasMoreElements(); ) {
    //      Cell key = (Cell)e.nextElement();
    //      pstream.println("(DEFTEMPLATE "+key);
    //      pstream.println(" "+(Cell)templateList.get(key));
    //      pstream.println(")");
    //    }

    //    // (DEFINST ...)の出力
    //    for ( Enumeration e=instList.keys(); e.hasMoreElements(); ) {
    //      Integer key = (Integer)e.nextElement();
    //      Vector inst = (Vector)instList.get(key);
    //      for ( int i=0; i<inst.size(); i++ ) {
    //	Cell c = (Cell)inst.get(i);
    //	pstream.println("(DEFINST "+c.car());
    //	pstream.println(" "+c.cdr());
    //	pstream.println(")");
    //      }
    //    }

    // (DEFINST ...)展開形の出力
    for ( Enumeration e=instList.keys(); e.hasMoreElements(); ) {
      Integer key = (Integer)e.nextElement();
      Vector inst = (Vector)instList.get(key);
      for ( int i=0; i<inst.size(); i++ ) {
	Cell c = (Cell)inst.get(i);
	macroEnv v;
	v = parseInstData(c.car(), c.cdr());
	dumpInstData(c.car(), c.cdr(), v, pstream);
      }
    }

  }

  /**
   * 中間表現のバイナリ形式をファイルに待避する。
   * @param tableFile	バイナリ形式ファイル名
   */
  public void SaveTables(String tableFile) throws IOException {
    FileOutputStream ostream = new FileOutputStream(tableFile);
    ObjectOutputStream p = new ObjectOutputStream(ostream);

    writeObject(p);
    ostream.close();
  }

  /**
   * 中間表現のバイナリ形式を読み込む。
   * @param tableFile	バイナリ形式ファイル名
   */
  public void RestoreTables(String tableFile) throws IOException, ClassNotFoundException {
    FileInputStream istream = new FileInputStream(tableFile);
    ObjectInputStream p = new ObjectInputStream(istream);

    /* 再初期化の準備 */
    cleanUp();
    InstHash.cleanUp();
    List.cleanUp();
    targetMethod.cleanUp();
    /* テーブルの読み込み */
    readObject(p);
    istream.close();
    /* 再初期化 */
    init();
    InstHash.init();
    List.init();
    targetMethod.init();
    /* 命令ハッシュ・テーブルの再構成 */
    Hashtable inst = instList;
    instList = new Hashtable();
    for ( Enumeration e = inst.elements(); e.hasMoreElements(); ) {
      Object v = e.nextElement();
      if ( v!=null ) {
	Cell c = ((Cell)((Vector)v).get(0)).cdr();
	Integer key = InstHash.hashValue(c);
	instList.put(key, v);
      }
    }

    // 中間表現パターン数を数える
    int patterns = 0;
    for ( Enumeration e=instList.keys(); e.hasMoreElements(); ) {
      Integer key = (Integer)e.nextElement();
      Vector v = (Vector)instList.get(key);
      patterns += v.size();
    }
    // 統計情報表示
    System.err.println("Pattern:");
    System.err.println("  "+tableFile+": "+templateList.size()+" templates, "
		       +nameList.size()+" names, "
		       +patterns+" patterns, "
		       +asmVec.size()+" languages");
  }

  /**
   * 中間表現をアセンブラ表記に変換する.
   * <p>アセンブラは、DEFLANGの0番目の指定を使う。
   * @param c		中間表現
   * @return		変換されたアセンブラ表記
   */
  public String[] convert(Cell c) {
    if ( asmVec.size()==0 ) return convert(c, null);
    else return convert(c, ((Cell)asmVec.get(0)).toString());
  }

  /**
   * 中間表現をアセンブラ表記に変換する.
   * <p>この形式では、アセンブラ種別が指定される。
   * @param c		中間表現
   * @param lang	アセンブラ指定
   * @return		変換されたアセンブラ表記
   */
  public String[] convert(Cell c, String lang) {
    Vector vs = new Vector();
    Cell[][] env = new Cell[10][]; // HOLEにマッチするCELL
    String[] tmp = new String[10]; // マクロ・テンプレートHOLEにマッチするテンプレート文字列
    String[] mTmp = new String[10]; // マクロ・テンプレート記述（??nx）
    Integer key = InstHash.hashValue(c); // 中間表現のハッシュ値
    if ( lang==null ) {
      langIndex = 0;	// デフォルトのアセンブラ
    } else {
      langIndex = asmVec.indexOf((Cell)List.atom(lang)); // アセンブラ指定
    }
    if ( !instList.containsKey(key) ) { // ハッシュ値に対応する中間表現を検索
      System.err.println("Pattern: there are no instruction candidates for "+c);
      return null;
    }
    Vector vec = (Vector)instList.get(key);
    for ( int i=0; i<vec.size(); i++ ) {
      Cell inst = (Cell)vec.get(i);
      if ( match(inst.cdr(), c, inst.car().nth(langIndex).toString(), env, tmp, mTmp) ) {
	if ( debMode!=0 ) {
	  System.out.println("convert: "+inst.car().nth(langIndex).toString());
	}
        vs.addElement(fill(inst.car().nth(langIndex), env, tmp));
      }
    }
    String[] s = new String[vs.size()];
    vs.copyInto(s);
    if ( vs.size()==0 ) {
      System.err.println("Pattern: there are no suitable instructions for "+c);
    }
    return s;
  }

  /******************/
  /* PRIVATE METHOD */
  /******************/
  /**
   * 中間形式記述の解析を行う。
   * <p>マクロ・テンプレートの解析も含まれている。
   * <p>解析結果は、各種テーブルに設定される。
   * @param lr		中間形式の入力Reader
   */
  private void parsePattern(ListReader lr) throws IOException {
    for(;;) {
      Cell c = lr.hashingRead();
      if ( c==null ) return;
      /*
	エラーチェック(NIL読み込み)
      */
      if ( c==List.nil ) {
	System.err.println("Pattern: Line "+lr.lineno()+": read NIL object");
	continue;
      }
      /*
	エラーチェック(ATOM読み込み)
      */
      if ( c.isAtom() ) {
	System.err.println("Pattern: Line "+lr.lineno()+": read some ATOM("+c.toString()+") object");
	continue;
      }
      /*
	DEFNAMEの処理
      */
      if ( c.car()==defnameCell ) {
	nameList.put(c.nth(1), c.nth(2));
      }
      /*
	DEFINSTの処理
	中間表現のhash値を計算し instHashTableに登録する。
      */
      if ( c.car()==definstCell ) {
	Cell tmps;
	if ( c.nth(1).isAtom() ) { // 単一言語指定の場合リスト化する
	  tmps = List.cons(c.nth(1), List.nil);
	} else {
	  tmps = c.nth(1);
	}
	if ( debMode!=0 ) {
	  System.out.println("parsePattern: DEFINST "+tmps);
	}
	Integer key = InstHash.hashValue(c.nth(2));
	Vector inst;
	if ( !instList.containsKey(key) ) {
	  inst = new Vector();
	  instList.put(key, inst);
	} else {
	  inst = (Vector)instList.get(key);
	  for ( int i=0; i<inst.size(); i++ ) {
	    if ( ((Cell)inst.get(i)).cdr()==c.nth(2) ) {
	      System.err.println("Pattern: \""+tmps.car().toString()+"\" has the identical form that \""+((Cell)inst.get(i)).car().car().toString()+"\" has.");
	    }
	  }
	}
	inst.add(List.cons(tmps, c.nth(2)));
      }
      /*
	DEFLANGの処理
	アセンブラ名称は asmVecに登録される。
      */
      if ( c.car()==deflangCell ) {
	for ( int i=0; c.nth(i+1)!=List.nil; i++ ) {
	  asmVec.add(i, c.nth(i+1));
	}
      }
      /*
	DEFTEMPLATEの処理
	テンプレートは templateListに登録される。
      */
      if ( c.car()==deftemplateCell ) {
	templateList.put(c.nth(1), c.nthcdr(2));
      }
    }
  }


  /**
   * パターン・マッチを行い、HOLEの対応を返す。
   * @param x		中間表現形式の命令記述
   * @param y		入力中間表現
   * @param tmp		テンプレート文字列
   * @param env		HOLEに対応するS式
   * @param tmps	マクロ・テンプレートに対応する文字列
   * @param mTmps	マクロ・テンプレート記述（??nx）
   * @return		xとyがmatchした場合はtrue
   */
  private boolean match(Cell x, Cell y, String tmp, Cell[][] env, String[] tmps, String[] mTmps) {
    for( int i=0; i<10; i++ ) {
      env[i] = null;
      tmps[i] = null;
      mTmps[i] = null;
    }
    return match1(x, y, tmp, -1, env, tmps, mTmps);
  }

  /**
   * パターン・マッチ(match)の補助関数。
   * @param x		中間表現形式の命令記述
   * @param y		入力中間表現
   * @param tmp		テンプレート文字列
   * @param offset	負の場合はトップレベル解析中、正の場合は解析中のマクロ・テンプレート番号
   * @param env		HOLEに対応するS式
   * @param tmps	マクロ・テンプレートに対応する文字列
   * @param mTmps	マクロ・テンプレート記述（??nx）
   * @return		xとyがmatchした場合はtrue
   */
  private boolean match1(Cell x, Cell y, String tmp, int offset, Cell[][] env, String[] tmps, String[] mTmps) {
    // x!=yの場合

    if ( debMode>=9 ) {
      System.out.println("match1: arg x: "+x);
      System.out.println("match1: arg y: "+y);
      System.out.println("match1: arg tmp: "+tmp);
      System.out.println("match1: (x==y) == "+(x==y));
    }

    while ( x!=y ) {
      if ( x.isAtom() ) return false;
      if ( x.car()==holeCell ) {
	if ( debMode>=9 ) {
	  System.out.println("match1: HOLE: "+x);
	}
	// 2001/06/25: 加藤
	//   整数値をLongAtomではなく、BigNumAtomで扱うよう修正した。
	//
	//        int n = (int)((LongAtom)x.nth(1)).value;
	int n = ((BigNumAtom)x.nth(1)).value.intValue(); // HOLE番号
	if ( offset<0 ) {	// マクロ・テンプレート外
	  int idx;
	  if ( (idx=isMacroTemplate(tmp, n))>=0 ) {
	    if ( matchMacroTemplate(x, y, tmp.substring(idx), offset, env, tmps, mTmps, n) ) return true;
	    else return false;
	  }
	  if ( env[n]!=null && !List.equal(env[n][0], y) ) return false;
	} else {		// マクロ・テンプレート内
	  if ( env[offset][n]!=null && !List.equal(env[offset][n], y) ) return false;
	}
        if ( !x.nthcdr(2).isAtom() ) {
          Cell z = (Cell)nameList.get(x.nth(2));
          if ( z==null ) return false;
          while ( !z.isAtom() ) {
            if ( z.car()==y ) break;
            z = z.cdr();
          }
          if ( z.isAtom() ) return false;
        }
	if ( offset<0 ) {
	  env[n] = new Cell[1];
	  env[n][0] = y;

	  if ( debMode>=5 ) {
	    System.out.println("match1: matched! env["+n+"][0] = "+y);
	  }

	} else {
	  env[offset][n] = y;

	  if ( debMode>=5 ) {
	    System.out.println("match1: matched! env["+offset+"]["+n+"] = "+y);
	  }

	}

        return true;
      }
      if ( y.isAtom() ) return false;
      if ( !match1(x.car(), y.car(), tmp, offset, env, tmps, mTmps) ) return false;
      x = x.cdr();
      y = y.cdr();
    }
    // x==yの場合
    return true;
  }

  /**
   * パターンマッチの補助関数。
   * マクロ・テンプレートのマッチングを行う。
   * @param x		中間表現形式の命令記述
   * @param y		入力中間表現
   * @param offset	負の場合はトップレベル解析中、正の場合は解析中のマクロ・テンプレート番号
   * @param env		HOLEに対応するS式
   * @param tmps	マクロ・テンプレートに対応する文字列
   * @param mTmps	マクロ・テンプレート記述（??nx）
   * @param n		マッチしたHOLE番号
   * @return		xとyがmatchした場合はtrue
   */
  private boolean matchMacroTemplate(Cell x, Cell y, String tmp, int offset, Cell[][] env, String[] tmps, String[] mTmps, int n) {
    int idx = 0;
    int val;
    Cell t;

    // 登録済みであることを確認する
    if ( (t=(Cell)templateList.get(List.atom(tmp.substring(idx+3, idx+4))))==null ) {
      System.err.println("Pattern: no such macro template: "+tmp.substring(idx, idx+4));
      return false;
    }
    // 最初の出現時に環境配列を用意する
    if ( env[n]==null ) {
      Cell[] tenv = new Cell[10];
      for( int i=0; i<10; i++ ) {
	tenv[i] = null;
      }
      env[n] = tenv;
      mTmps[n] = tmp.substring(idx, idx+4);
    } else {
      // デバッグ・メッセージ
      //System.err.println("Pattern: macro template: "+tmp.substring(idx, idx+4)+" "+mTmps[n]);
      //
      if ( mTmps[n].compareTo(tmp.substring(idx, idx+4))!=0 ) {	// マクロ・テンプレート記述（??nx）の形が一致しない
	System.err.println("Pattern: inconsistent macro template: "+tmp.substring(idx, idx+4)+" "+mTmps[n]);
	return false;
      }
    }
    // マッチする定義を検索する
    for ( int i=0; t.nth(i)!=List.nil; i++ ) {
      
      if ( debMode>=9 ) {
	System.out.println("matchMacroTemplate: y = "+y);
	System.out.println("matchMacroTemplate: pat = "+t.nth(i).nth(1));
	System.out.println("matchMacroTemplate: template = "+t.nth(i).nth(0));
      }

      if ( match1(t.nth(i).nth(1), y, t.nth(i).nth(0).toString(), n, env, tmps, mTmps) ) {
	if ( debMode>=3 ) {
	  System.out.println("matchMacroTemplate: y = "+y);
	  System.out.println("matchMacroTemplate: pat = "+t.nth(i).nth(1));
	  System.out.println("matchMacroTemplate: template = "+t.nth(i).nth(0));
	}
	/* テンプレートの設定 */
	if ( t.nth(i).nth(0).isAtom() ) {
	  tmps[n] = t.nth(i).nth(0).toString();
	} else {
	  tmps[n] = t.nth(i).nth(0).nth(langIndex).toString();
	}
	return true;
      }
    }
    if ( debMode!=0 ) {
      System.out.println("Pattern: the macro template ("+tmp.substring(idx, idx+4)+") does not match "+y);
    }
    env[n] = null;
    return false;
  }

  /**
   * パターンマッチの補助関数。
   * <p>HOLE番号に対応するテンプレートが、マクロ・テンプレートかどうかの判断を行う。
   * @param tmp		テンプレート
   * @param n		HOLE番号
   * @return		マクロ・テンプレートでない場合は負、マクロ・テンプレートの場合はtmp内のテンプレート指定のインデックス
   */
  private int isMacroTemplate(String tmp, int n) {
    int idx = 0;
    int val;
    while ( (idx=tmp.indexOf('?', idx))>=0 ) {
      if ( tmp.charAt(idx+1)=='?' ) {
	val = tmp.charAt(idx+2)-'0';
	if ( val==n ) {	// HOLEにマッチするマクロ・テンプレート
	  return idx;
	}
	idx += 4;
      } else {
	idx += 3;
      }
    }
    return -1;
  }

  /**
   * アセンブラ出力の穴を埋める。
   * @param c		中間表現リスト
   * @param env		環境
   * @param tmps	マクロ・テンプレート文字列
   * @return		展開された命令文字列
   */
  private String fill(Cell c, Cell[][] env, String[] tmps) {
    String s = c.toString();
    String r = "";
    String v = fill1(r, s, -1, env, tmps);

    if ( debMode>=9 ) {
      System.out.println("fill: s "+s);
      System.out.println("fill: v "+v);
    }
    return v;
  }

  /**
   * アセンブラ出力の穴を埋める。
   * fill()のサブ関数である。
   * @param r		展開された命令文字列
   * @param s		ソース・テンプレート
   * @param offset	マクロ・テンプレートHOLE番号のオフセット値
   * @param env		環境
   * @param tmps	マクロ・テンプレート文字列
   * @return		展開された命令文字列
   */
  private String fill1(String r, String s, int offset, Cell[][] env, String[] tmps) {
    for( int i=0; i<s.length(); i++ ) {
      if ( s.charAt(i)=='?' && i<s.length()-2 ) { // HOLE
	if ( s.charAt(i+1)!='?' ) { // 通常のHOLE
	  if ( debMode>=3 ) {
	    System.out.println("fill1: r "+r+" s "+s);
	    System.out.println("fill1: offset "+offset);
	    System.out.println("fill1: HOLE "+s.charAt(i)+s.charAt(i+1)+s.charAt(i+2));
	  }
	  if ( offset<0 ) {	// マクロ・テンプレート外
	    if ( env[s.charAt(i+1)-'0']==null ) {
	      System.err.println("Pattern: there are no HOLE cells numbered "+(s.charAt(i+1)-'0'));
	      r += s.charAt(i);
	    } else {
	      r += targetMethod.convertHole(env[s.charAt(i+1)-'0'][0], s.charAt(i+2));
	      i += 2;
	    }
	  } else {		// マクロ・テンプレート内
	    if ( env[offset][s.charAt(i+1)-'0']==null ) {
	      System.err.println("Pattern: there are no HOLE cells numbered ["+offset+"]["+(s.charAt(i+1)-'0')+"]");
	      r += s.charAt(i);
	    } else {
	      r += targetMethod.convertHole(env[offset][s.charAt(i+1)-'0'], s.charAt(i+2));
	      i += 2;
	    }
	  }
	} else {		// マクロ・テンプレートのHOLE
	  int off = s.charAt(i+2)-'0';

	  if ( debMode>=3 ) {
	    System.out.println("fill1: s "+s);
	    System.out.print("fill1: tmps ");
	    for ( int j=0; j<10; j++ )
	      System.out.print(" tmps["+j+"] "+tmps[j]);
	    System.out.println();
	  }

	  r = fill1(r, tmps[off], off, env, tmps);
	  i += 3;
	}
      } else {			// その他
        r += s.charAt(i);
      }
    }
    return r;
  }

  /**
   * オブジェクト出力ストリームからに各種テーブルを書き込む。
   * @param out		オブジェクト出力ストリーム
   */
  private void writeObject(java.io.ObjectOutputStream out) throws IOException {
    out.writeObject(asmVec);	// アセンブラ言語テーブル
    out.writeObject(nameList);	// 記号定義テーブル
    out.writeObject(instList);	// 命令テーブル
    out.writeObject(templateList); // マクロ・テンプレート・テーブル
    out.flush();
  }

  /**
   * オブジェクト入力ストリームからのオブジェクト入力処理を行う。
   * @param in		オブジェクト入力ストリーム
   */
  private void readObject(java.io.ObjectInputStream in) throws IOException, ClassNotFoundException {
    asmVec = (Vector)in.readObject(); // アセンブラ言語テーブル
    nameList = (Hashtable)in.readObject(); // 記号定義テーブル
    instList = (Hashtable)in.readObject(); // 命令テーブル
    templateList = (Hashtable)in.readObject(); // マクロ・テンプレート・テーブル
  }


  /**
   * マクロ・テンプレート展開のためのデータ
   */
  private class macroEnv {
    public Vector[] template = new Vector[10];
    public Vector[] body = new Vector[10];

    public int[] indexMax = new int[10];
    public int[] indexBase = new int[10];
    public int[] noOfMacro = new int[10];
    public int[] curMacro = new int[10];

    {
      int i;
      for ( i=0; i<10; i++ ) {
	template[i] = new Vector();
	body[i] = new Vector();
	indexBase[i] = 0;
	noOfMacro[i] = 0;
	curMacro[i] = 0;
      }
    }

    public Cell getTemplate(int hole) {
      if ( template[hole].get(curMacro[hole])==null ) {
	return List.nil;
      } else {
	return (Cell)template[hole].get(curMacro[hole]);
      }
    }

    public Cell getBody(int hole) {
      if ( body[hole].get(curMacro[hole])==null ) {
	return List.nil;
      } else {
	return (Cell)body[hole].get(curMacro[hole]);
      }
    }

    public boolean updateIndex() {
      int i;
      // マクロ・テンプレートのパターン・インデックスを更新
      for ( i=9; i>=0; i-- ) {
	if ( noOfMacro[i]!=0 ) {	// マクロ・テンプレート
	  curMacro[i]++;
	  break;
	}
      }
      if ( i<0 ) return false;	// マクロ・テンプレート無し
      if ( debMode>0 ) {
	System.out.print("env.updateIndex: ");
      }
      // 更新値を確認し、展開の終了を判断
      for ( i=9; i>=0; i-- ) {
	if ( debMode>0 ) {
	  System.out.print(curMacro[i]+" "+noOfMacro[i]+" ");
	}
	if ( noOfMacro[i]!=0 && curMacro[i]>=noOfMacro[i] ) {
	  int j;
	  curMacro[i] = 0;
	  for ( j=i-1; j>=0; j-- ) {
	    if ( noOfMacro[j]!=0 ) {
	      curMacro[j]++;
	      break;
	    }
	  }
	  if ( j<0 ) return false; // 展開完了
	}
      }
      if ( debMode>0 ) {
	System.out.println("");
      }
      return true;		// 展開未完了
    }

  }

  /**
   * 中間形式展開のため、命令パターンを解析し、中間形式展開データを作成する。
   * @param template	テンプレート文字列のリスト
   * @param body	中間形式
   * @return	中間形式展開のためのデータ構造
   */
  private macroEnv parseInstData(Cell template, Cell body) {
    String temp = template.car().toString(); // 最初のテンプレートを使って解析
    macroEnv env = new macroEnv();

    parseInstTemplate(temp, -1, env);

    return env;
  }

  /**
   * テンプレート文字列を解析して中間形式展開データを作成する。
   * @param env		中間形式展開データ
   * @param hole	現在処理中のHOLEインデックス(負の場合はトップレベル)
   * @param env		中間形式展開データ
   */
  private void parseInstTemplate(String s, int hole, macroEnv env) {
    Cell t;
    int i, j;
    int h;

    if ( debMode>0 ) {
      System.out.println("parseInstTemplate: \""+s+"\" "+hole);
    }
    for( i=0; i<s.length(); i++ ) {
      if ( s.charAt(i)=='?' && i<s.length()-2 ) { // HOLE
	if ( s.charAt(i+1)=='?' ) { // マクロ・テンプレートのHOLE
	  if ( (t=(Cell)templateList.get(List.atom(s.substring(i+3, i+4))))==null ) {
	    System.err.println("Pattern: no such macro template: "+s.substring(i, i+4));
	    return;
	  }
	  h = s.charAt(i+2)-'0';
	  for ( j=0; t.nth(j)!=List.nil; j++ ) {
	    env.template[h].add(t.nth(j).nth(0));
	    env.body[h].add(t.nth(j).nth(1));
	  }
	  env.noOfMacro[h] = j;	// テンプレートの定義数
      	  i += 3;
	} else {		// 通常のHOLE
	  i += 2;
	}
      }
    }

  }

  /**
   * 中間形式展開用データを使って中間形式を展開する。
   * @param template	テンプレート文字列のリスト
   * @param body	中間形式
   * @param env		中間形式展開データ
   * @param pstream	ダンプ先ファイル
   */
  private void dumpInstData(Cell template, Cell body, macroEnv env, PrintStream pstream) {

    if ( debMode>0 ) {
      System.out.println("dumpInstData: ");
    }
    do {
      dumpAnInstData(template, body, env, pstream);
    } while ( env.updateIndex() );

  }

  /**
   * 中間形式の１命令を展開する。
   * @param template	テンプレート文字列のリスト
   * @param body	中間形式
   * @param env		中間形式展開データ
   * @param pstream	ダンプ先ファイル
   * @return	中間形式展開のためのデータ構造
   */
  private void dumpAnInstData(Cell template, Cell body, macroEnv env, PrintStream pstream) {
    // HOLEのインデックス・ベース値を計算
    calcHoleMaxIndex(template.car().toString(), -1, env);
    calcHoleIndexBase(env);
    // １定義を展開する
    pstream.print("(DEFINST ");
    // テンプレート文字列を展開する
    pstream.print("(");
    dumpInstTemplate(template, env, pstream);
    pstream.println(")");
    // 中間形式定義を展開する
    pstream.print(" ");
    dumpInstBody(body, -1, env, pstream);
    pstream.println("\n)\n");
  }

  /**
   * マクロ・テンプレートに含まれるHOLE番号の最大値を計算する。
   * @param template	テンプレート文字列
   * @param env		中間形式展開データ
   */
  private void calcHoleMaxIndex(String s, int hole, macroEnv env) {
    int max = 0;
    for( int i=0; i<s.length(); i++ ) {
      if ( s.charAt(i)=='?' && i<s.length()-2 ) { // HOLE
	if ( s.charAt(i+1)=='?' ) { // マクロ・テンプレートのHOLE
	  int h = s.charAt(i+2)-'0';
	  String str = ((Cell)(env.template[h].get(env.curMacro[h]))).car().toString();
	  calcHoleMaxIndex(str, h, env);
	  i += 3;
	} else {
	  if ( max<s.charAt(i+1)-'0' ) {
	    max = s.charAt(i+1)-'0';
	  }
	  i += 2;
	}
      }
    }
    if ( hole>=0 ) {
      env.indexMax[hole] = max;
    }
  }

  /**
   * HOLE番号の再計算を行う。
   * @param env		中間形式展開データ
   */
  private void calcHoleIndexBase(macroEnv env) {
    int sum = 0;

    if ( debMode>0 ) {
      System.out.print("calcHoleIndexBase: ");
    }
    for ( int i=0; i<10; i++ ) {
      if ( debMode>0 ) {
	System.out.print(i+" ");
      }
      env.indexBase[i] = i+sum;
      if ( env.noOfMacro[i]>0 ) sum += env.indexMax[i];
    }
    if ( debMode>0 ) {
      System.out.println("");
    }
  }

  /**
   * テンプレート文字列を展開する。
   * @param template	テンプレート文字列のリスト
   * @param body	中間形式
   * @param env		中間形式展開データ
   * @param pstream	ダンプ先ファイル
   * @return	中間形式展開のためのデータ構造
   */
  private void dumpInstTemplate(Cell template, macroEnv env, PrintStream pstream) {
    for ( int i=0; template.nth(i)!=List.nil; i++ ) {
      String s = template.nth(i).toString();
      pstream.print("\"");	// 文字列の先頭
      dumpAInstTemplate(s, -1, i, env, pstream);
      pstream.print("\"");	// 文字列の後尾
      if ( template.nth(i+1)!=List.nil )
	pstream.print(" ");
    }
  }

  /**
   * 1つのテンプレート文字列を展開し、中間形式展開データに反映させる。
   * @param s		テンプレート文字列
   * @param hole	現在処理中のHOLEインデックス(負ならトップレベル)
   * @param lang	言語インデックス
   * @param env		中間形式展開データ
   * @param pstream	ダンプ先ファイル
   */
  private void dumpAInstTemplate(String s, int hole, int lang, macroEnv env, PrintStream pstream) {
    if ( debMode>0 ) {
      System.out.println("dumpAInstTemplate: "+s+" "+hole);
    }
    // テンプレートを出力
    for( int i=0; i<s.length(); i++ ) {
      // 2001/07/10: 加藤
      //   制御文字のエスケース処理を行っていなかった。
      //
      if ( Character.isISOControl(s.charAt(i)) ) { // コントロール文字のエスケープ
	switch ( s.charAt(i) ) {
	case '\b':
	  pstream.print("\\b");
	  break;
	case '\n':
	  pstream.print("\\n");
	  break;
	case '\f':
	  pstream.print("\\f");
	  break;
	case '\r':
	  pstream.print("\\r");
	  break;
	case '\"':
	  pstream.print("\\\"");
	  break;
	case '\'':
	  pstream.print("\\\\");
	  break;
	default:
	  pstream.print("\\"+Integer.toString((int)s.charAt(i), 8));
	  break;
	}
      } else if ( s.charAt(i)=='?' && i<s.length()-2 ) { // HOLE
	if ( s.charAt(i+1)=='?' ) { // マクロ・テンプレートのHOLE
	  int h = s.charAt(i+2)-'0';
	  String str = ((Cell)(env.template[h].get(env.curMacro[h]))).nth(lang).toString();
	  dumpAInstTemplate(str, h, lang, env, pstream);
	  i += 3;
	} else {
	  pstream.print(s.charAt(i));
	  if ( hole>=0 ) {	// マクロ・テンプレートの中
	    int val = s.charAt(i+1)-'0'+env.indexBase[hole];
	    pstream.print(val);
	  } else {
	    int val = env.indexBase[s.charAt(i+1)-'0'];
	    if ( debMode>0 ) {
	      System.out.println("dumpAInstTemplate: hole "+s.charAt(i+1)+" val "+val);
	    }
	    pstream.print(val);
	  }
	  pstream.print(s.charAt(i+2));
	  i += 2;
	}
      } else {			// その他
	pstream.print(s.charAt(i));
      }
    }
  }

  /**
   * 中間形式のbody部を展開する。
   * @param body	中間形式
   * @param hole	現在処理中のHOLEインデックス(負ならトップレベル)
   * @param env		中間形式展開データ
   * @param pstream	ダンプ先ファイル
   */
  private void dumpInstBody(Cell body, int hole, macroEnv env, PrintStream pstream) {
    if ( body.car()==holeCell ) { // HOLEセル
      // 数値はBigNumAtomを使っている
      //int idx = (int)((LongAtom)body.nth(1)).value;
      int idx = ((BigNumAtom)body.nth(1)).value.intValue();
      //
      if ( hole>=0 ) {		// マクロ・テンプレートの中
	  pstream.print("(HOLE ");
	  int v = idx+env.indexBase[hole];
	  pstream.print(v);
	  if ( body.nth(2)!=List.nil ) {
	    pstream.print(" "+body.nth(2));
	  }
	  pstream.print(")");
      } else {			// トップレベル
	if ( debMode>0 ) {
	  System.out.println("dumpInstBody: idx "+idx+" noOfMacro "+env.noOfMacro[idx]);
	}
	if ( env.noOfMacro[idx]==0 ) { // 通常のテンプレート
	  pstream.print("(HOLE ");
	  int v = env.indexBase[idx];
	  pstream.print(v);
	  if ( body.nth(2)!=List.nil ) {
	    pstream.print(" "+body.nth(2));
	  }
	  pstream.print(")");
	} else {			// マクロ・テンプレート
	  dumpInstBody(env.getBody(idx), idx, env, pstream);
	}
      }
    } else {			// HOLE以外のセル
      pstream.print("(");
      if ( body.car().isAtom() ) { // carがatomの場合
	pstream.print(body.car().toString());
	if ( body.cdr()!=List.nil ) pstream.print(" ");
	dumpRestOfInstBody(body.cdr(), hole, env, pstream);
      } else {			// carがリストの場合
	dumpInstBody(body.car(), hole, env, pstream);
	if ( body.cdr()!=List.nil ) pstream.print(" ");
	dumpRestOfInstBody(body.cdr(), hole, env, pstream);
      }
    }
  }

  /**
   * 中間表現リストのcdr部をダンプする。
   * @param body	中間表現本体
   * @param hole	現在処理中のHOLEインデックス(負ならトップレベル)
   * @param env		中間形式展開データ
   * @param pstream	ダンプ先ファイル
   */
  private void dumpRestOfInstBody(Cell body, int hole, macroEnv env, PrintStream pstream) {
    if ( body.isAtom() ) { // bodyの終了
      pstream.print(")");
      return;
    } else if ( body.car()==holeCell ) { // HOLEセルはdumpInstBodyにまかせる。
      dumpInstBody(body.car(), hole, env, pstream);
      if ( body.cdr()!=List.nil ) pstream.print(" ");
      dumpRestOfInstBody(body.cdr(), hole, env, pstream);
    } else {			// HOLE以外のセルはそのまま表示
      if ( body.car().isAtom() ) { // carがatomの場合はそのまま表示
	pstream.print(body.car().toString());
	if ( body.cdr()!=List.nil ) pstream.print(" ");
	dumpRestOfInstBody(body.cdr(), hole, env, pstream);
      } else {			// carがリストの場合は再帰呼び出し
	dumpInstBody(body.car(), hole, env, pstream);
	if ( body.cdr()!=List.nil ) pstream.print(" ");
	dumpRestOfInstBody(body.cdr(), hole, env, pstream);
      }
    }
  }

}