*** empty log message ***

[m17n/m17n-lib-cs.git] / MInputMethod.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Reflection;
using System.IO;
using System.Xml;

using M17N;
using M17N.Core;
using M17N.Input;

using Xex = System.Xml.Expression.Xexpression;

namespace M17N.Input
{
  public class MInputMethod
  {
    // Delegaes
    public delegate bool Callback (Context ic, MPlist args);

    // Class members
    public static Callback PreeditStart, PreeditDone, PreeditDraw;
    public static Callback StatusStart, StatusDone, StatusDraw;
    public static Callback CandidateStart, CandidateDone, CandidateDraw;
    public static Callback SetSpot;
    public static Callback Toggle;
    public static Callback Reset;
    public static Callback GetSurroundingText;
    public static Callback DeleteSurroundingText;

    internal static Xex.Domain im_domain = new Xex.Domain (null);
    private static MSymbol Minput_method = "input-method";
    private static MSymbol Mdescription = "description";
    private static MSymbol Mvariable = "variable";
    private static MSymbol Mcommand = "command";
    private static MSymbol Mmodule = "module";
    private static MSymbol Mtitle = "title";
    private static MSymbol Minclude = "include";
    private static MSymbol Mmacro = "macro";
    private static MSymbol Mmap = "map";
    private static MSymbol Mmap_list = "map-list";
    private static MSymbol Mstate = "state";
    internal static MSymbol Mcandidates = "candidates";
    private static MSymbol Minsert = "insert";
    internal static MSymbol Mselect = "select";
    private static MSymbol Mdelete = "delete";
    private static MSymbol Mmove = "move";
    private static MSymbol Mmark = "mark";
    private static MSymbol Mmarker = "marker";
    private static MSymbol Mset = "set";
    private static MSymbol Madd = "add";
    private static MSymbol Msub = "sub";
    private static MSymbol Mmul = "mul";
    private static MSymbol Mdiv = "div";
    private static MSymbol Mif = "if";
    private static MSymbol Mcond = "cond";
    private static MSymbol Mchar_at = "char-at";
    private static MSymbol Msurrounding_flag = "surrounding-text-flag";
    private static MSymbol Mpushback = "pushback"; 
    private static MSymbol Mkeyseq = "keyseq"; 

    private static MSymbol Mget_surrounding_text = "get-surrounding-text";
    private static MSymbol Mdel_surrounding_text = "del-surrounding-text";

    private static MSymbol Mat_minus_zero = "@-0";

    private static Xex.Symbol Qmap = "map";
    private static Xex.Symbol Qrule = "rule";
    private static Xex.Symbol Qkeyseq = "keyseq";
    private static Xex.Symbol Qprogn = "progn";
    private static Xex.Symbol Qinsert = "insert";
    private static Xex.Symbol Qinsert_candidates = "insert-candidates";
    private static Xex.Symbol Qchar_at = "char-at";
    private static Xex.Symbol Qsname = "sname";
    private static Xex.Symbol Qmname = "mname";
    private static Xex.Symbol Qstate_hook = "state-hook";
    private static Xex.Symbol Qcatch_all_branch = "catch-all-branch";
    private static Xex.Symbol Qbranch = "branch";
    private static Xex.Symbol Qstate = "state";
    private static Xex.Symbol Qtitle = "title";


    private static Xex.Term Tnil = new Xex.Term ((Xex.Symbol) "nil");
    private static Xex.Term Tcatch_tag = new Xex.Term ((Xex.Symbol) "@mimtag");

    private static Dictionary<MDatabase.Tag, MInputMethod> im_table
      = new Dictionary<MDatabase.Tag, MInputMethod> ();

    internal static MInputMethod im_global = null;

    [FlagsAttribute]
    private enum LoadStatus
    {
      None =   0x00,
      Header = 0x01,
      Body =   0x02,
      Full =   0x03,
      Error =  0x04,
    };

    [FlagsAttribute]
    public enum ChangedStatus
    {
      None =            0x00,
      StateTitle =      0x01,
      Preedit    =      0x02,
      CursorPos =       0x04,
      CandidateList =   0x08,
      CandidateIndex =  0x10,
      CandidateShow =   0x20,
    }

    private static ChangedStatus CandidateAll = (ChangedStatus.CandidateList
                                                 | ChangedStatus.CandidateIndex
                                                 | ChangedStatus.CandidateShow);
    [FlagsAttribute]
    public enum KeyModifier
      {
        None =      0x00000000,
        Shift_L =   0x00400000,
        Shift_R =   0x00800000,
        Shift =     0x00C00000,
        Control_L = 0x01000000,
        Control_R = 0x02000000,
        Control   = 0x03000000,
        Alt_L =     0x04000000,
        Alt_R =     0x08000000,
        Alt =       0x0C000000,
        AltGr =     0x10000000,
        Super =     0x20000000,
        Hyper =     0x40000000,
        High =      0x70000000,
        All =       0x7FC00000,
      };

    public struct Key
    {
      internal uint key;

      private static Dictionary<string, uint> keysyms
        = new Dictionary<string, uint> ();
      private static Dictionary<string, KeyModifier> keymodifiers
        = new Dictionary<string, KeyModifier> ();
      private static uint keysym_base = 0x200000;
      private static uint char_mask = ~((uint) KeyModifier.All);
      public static Key Reload;

      static Key ()
      {
        keysyms["bs"] = keysyms["backspace"] = 0x08;
        keysyms["tab"] = 0x09;
        keysyms["lf"] = keysyms["linefeed"] = 0x10;
        keysyms["cr"] = keysyms["return"] = keysyms["enter"] = 0x13;
        keysyms["esc"] = keysyms["escape"] = 0x1B;
        keysyms["spc"] = keysyms["space"] = 0x20;
        keysyms["del"] = keysyms["delete"] = 0x7F;
        keymodifiers["shift-l"] = KeyModifier.Shift_L;
        keymodifiers["shift-r"] = KeyModifier.Shift_R;
        keymodifiers["shift"] = KeyModifier.Shift;
        keymodifiers["control-l"] = KeyModifier.Control_L;
        keymodifiers["control-r"] = KeyModifier.Control_R;
        keymodifiers["control"] = KeyModifier.Control;
        keymodifiers["alt-l"] = KeyModifier.Alt_L;
        keymodifiers["alt-r"] = KeyModifier.Alt_R;
        keymodifiers["alt"] = KeyModifier.Alt;
        keymodifiers["altgr"] = KeyModifier.AltGr;
        keymodifiers["super"] = KeyModifier.Super;
        keymodifiers["hyper"] = KeyModifier.Hyper;
        Reload = new Key (keysym_base);
        keysyms["-reload"] = keysym_base++;
      }

      private static uint decode_keysym (MSymbol keysym)
      {
        uint key;
        string name = keysym.Name;

        if (name.Length == 1)
          return name[0];
        name = name.ToLower ();
        if (! keysyms.TryGetValue (name, out key))
          keysyms[name] = key = keysym_base++;
        return key;
      }

      private static uint combine_modifiers (uint c, KeyModifier modifiers)
      {
        if (c < 0x7F && c != 0x20)
          {
            if ((modifiers & KeyModifier.Shift) != KeyModifier.None
                && Char.IsLower ((char) c))
              {
                modifiers &= ~KeyModifier.Shift;
                c = Char.ToUpper ((char) c);
              }
            if ((modifiers & KeyModifier.Control) != KeyModifier.None)
              {
                modifiers &= ~KeyModifier.Control;
                c &= 0x1F;
              }
          }     
        return c | (uint) modifiers;
      }

      public Key (uint c) { key = c; }
      public Key (int c) { key = (uint) c; }

      public Key (uint c, KeyModifier modifiers)
      {
        key = combine_modifiers (c, modifiers);
      }

      public Key (MSymbol keysym, KeyModifier modifiers)
      {
        key = combine_modifiers (decode_keysym (keysym), modifiers);
      }

      public Key (MSymbol keysym)
      {
        string str = keysym.Name;
        int len = str.Length;
        int i;
        KeyModifier modifiers = KeyModifier.None;

        for (i = 0; i + 2 < len && str[i + 1] == '-'; i += 2)
          {
            if (str[i] == 'S')
              modifiers |= KeyModifier.Shift;
            else if (str[i] == 'C')
              modifiers |= KeyModifier.Control;
            else if (str[i] == 'A')
              modifiers |= KeyModifier.Alt;
            else if (str[i] == 'G')
              modifiers |= KeyModifier.AltGr;
            else if (str[i] == 's')
              modifiers |= KeyModifier.Super;
            else if (str[i] == 'H')
              modifiers |= KeyModifier.Hyper;
          }
        if (i + 1 == len)
          key = combine_modifiers (str[i], modifiers);
        else
          key = combine_modifiers (decode_keysym (keysym), modifiers);
      }

      public Key (MPlist plist)
      {
        KeyModifier modifiers = KeyModifier.None;
        MPlist p;

        for (p = plist; ! p.IsEmpty; p = p.next)
          {
            if (p.IsInteger)
              {
                if (! p.next.IsEmpty)
                  throw new Exception ("Invalid Key: " + plist);
                break;
              }
            else if (! p.IsSymbol)
              throw new Exception ("Invalid Key: " + plist);
            else
              {
                string name = p.Symbol.Name.ToLower ();
                KeyModifier m;
                
                if (! keymodifiers.TryGetValue (name, out m))
                  break;
                modifiers |= m;
              }
          }
        if (p.IsEmpty || ! p.next.IsEmpty)
          throw new Exception ("Invalid Key: " + plist);
        if (p.IsInteger)
          key = combine_modifiers ((uint) p.Integer, modifiers);
        else
          key = combine_modifiers (decode_keysym (p.Symbol), modifiers);
      }

      public bool HasModifier
      {
        get { return ((key & (uint) KeyModifier.All) != 0); }
      }

      public static bool operator== (Key k1, Key k2)
        {
          return k1.key == k2.key;
        }

      public static bool operator!= (Key k1, Key k2)
        {
          return k1.key != k2.key;
        }

      public override bool Equals (object o) { return key == ((Key) o).key; }

      public override int GetHashCode () { return (int) key; }

      public bool Match (Key k)
      {
        if (k.key == key)
          return true;
        if ((k.key & char_mask) != (key & char_mask))
          return false;
        KeyModifier m1 = ((KeyModifier) key) & KeyModifier.All;
        KeyModifier m2 = ((KeyModifier) k.key) & KeyModifier.All;
        return (((m1 & KeyModifier.Shift) == (m2 & KeyModifier.Shift)
                 || ((m1 & KeyModifier.Shift) == KeyModifier.Shift
                     && (m2 & KeyModifier.Shift) != KeyModifier.None))
                && ((m1 & KeyModifier.Control) == (m2 & KeyModifier.Control)
                    || ((m1 & KeyModifier.Control) == KeyModifier.Control
                        && (m2 & KeyModifier.Control) != KeyModifier.None))
                && ((m1 & KeyModifier.Alt) == (m2 & KeyModifier.Alt)
                    || ((m1 & KeyModifier.Alt) == KeyModifier.Alt
                        && (m2 & KeyModifier.Alt) != KeyModifier.None))
                && ((m1 & KeyModifier.High) == (m2 & KeyModifier.High)));
      }

      public int ToChar ()
      {
        return key & 0x1FFFFF;
      }

      public override string ToString ()
      {
        string str = Char.ToString ((char) key);
        KeyModifier m = ((KeyModifier) key) & KeyModifier.All;

        if (m != KeyModifier.None)
          {
            if ((m & KeyModifier.Shift) != KeyModifier.None)
              str = "S-" + str;
            if ((m & KeyModifier.Control) != KeyModifier.None)
              str = "C-" + str;
            if ((m & KeyModifier.Alt) != KeyModifier.None)
              str = "A-" + str;
            if ((m & KeyModifier.AltGr) != KeyModifier.None)
              str = "G-" + str;
            if ((m & KeyModifier.Super) != KeyModifier.None)
              str = "s-" + str;
            if ((m & KeyModifier.Hyper) != KeyModifier.None)
              str = "H-" + str;
          }
        return str;
      }
    }

    internal class KeySeq : Xex.TermValue
    {
      public List<Key> keyseq = new List<Key> ();

      public override Xex.TermValue Clone ()
      {
        KeySeq ks = new KeySeq ();
        ks.keyseq.InsertRange (0, keyseq);
        return ks;
      }

      public KeySeq () { }

      public KeySeq (MPlist plist)
      {
        foreach (MPlist p in plist)
          {
            if (p.IsSymbol)
              keyseq.Add (new Key (p.Symbol));
            else if (p.IsInteger)
              keyseq.Add (new Key ((char) p.Integer));
            else if (p.IsPlist)
              keyseq.Add (new Key (p.Plist));
            else
              throw new Exception ("Invalid Key Sequence: " + plist);
          }
      }

      public KeySeq (MText mt) : base ()
      {
        for (int i = 0; i < mt.Length; i++)
          keyseq.Add (new Key ((uint) mt[i]));
      }

      public KeySeq (List<Xex.Term> list)
        {
          int len = list.Count;

          for (int i = 0; i < len; i++)
            {
              if (list[i].IsInt)
                keyseq.Add (new Key (list[i].Intval));
              else if (list[i].IsStr)
                keyseq.Add (new Key (list[i].Strval));
              else if (list[i].IsSymbol)
                keyseq.Add (new Key ((string) list[i].Symval));
              else
                throw new Exception ("Invalid key: " + list[i]);
            }
        }

      public static Xex.TermValue parser (Xex.Domain domain, XmlNode node)
        {
          Xex.Term term = new Xex.Term (domain, node.FirstChild).Eval (domain);
          return (term.IsStr ? new KeySeq ((MText) term.Strval)
                  : new KeySeq (term.Listval));
        }

      public override string ToString ()
      {
        string str;

        foreach (Key key in keyseq)
          if (key.HasModifier)
            {
              str = "(keyseq";
              foreach (Key k in keyseq)
                str += " " + k.ToString ();
              return str + ")";
            }
        str = "\"";
        foreach (Key key in keyseq)             
          str += key.ToString ();
        return str + "\"";
      }
    }

    public class Command
    {
      public MSymbol name;
      public MText description;
      internal List<KeySeq> keys;

      public Command (MPlist p)
      {
        name = p.Symbol;
        p = p.Next;
        description = parse_description (p);
        if (description == null)
          description = "No description";
        keys = new List<KeySeq> ();
        Console.WriteLine ("cmd:" + p);
        for (p = p.next; ! p.IsEmpty; p = p.next)
          {
            if (p.IsMText)
              keys.Add (new KeySeq (p.Text));
            else if (p.IsPlist)
              keys.Add (new KeySeq (p.Plist));
          }
      }

      public Command (XmlNode node)
      {
        name = node.Attributes[0].Value;
        keys = new List<KeySeq> ();
        for (node = node.FirstChild; node != null; node = node.NextSibling)
          {
            if (node.Name == "description")
              description = parse_description (node);
            else if (node.Name == "keyseq")
              keys.Add ((KeySeq) KeySeq.parser (null, node));
          }
      }

      public override string ToString ()
      {
        string str = "(" + name + " \"" + (string) description;
        foreach (KeySeq keyseq in keys)
          str += " " + keyseq;
        return str + ")";
      }
    }

    internal class Plugin
    {
      private string name;
      private Assembly assembly;
      private Type plugin_type;

      public Plugin (string name)
      {
        this.name = name;
      }

      public MethodInfo GetMethod (Xex.Symbol name)
      {
        if (assembly == null)
          {
            assembly = Assembly.LoadFrom (name + ".dll");
            plugin_type = assembly.GetType ("M17n.MInputMethod.Plugin");
          }

        MethodInfo info = plugin_type.GetMethod ((string) name);
        if (info == null)
          throw new Exception ("Invalid plugin method: " + name);
        return info;
      }

      public override string ToString ()
      {
        return String.Format ("(module {0}", name);
      }
    }

    internal class PluginMethod : Xex.Function
    {
      private Plugin plugin;
      private MethodInfo method_info;
      object[] parameters = new object[2];

      public PluginMethod (Plugin plugin, string name)
        : base ((Xex.Symbol) name, 0, -1)
        {
          this.plugin = plugin;
        }

      public override Xex.Term Call (Xex.Domain domain, Xex.Variable vari,
                                     Xex.Term[] args)
      {
        args = (Xex.Term[]) args.Clone ();
        for (int i = 0; i < args.Length; i++)
          {
            args[i] = args[i].Eval (domain);
            if (domain.Thrown)
              return args[i];
          }
        if (method_info == null)
          method_info = plugin.GetMethod (name);
        parameters[0] = domain.context;
        parameters[1] = args;
        return (Xex.Term) method_info.Invoke (null, parameters);
      }
    }

    internal abstract class Marker : Xex.TermValue
    {
      private MSymbol name;

      private Marker (MSymbol name)
        {
          this.name = name;
        }

      public abstract int Position (Context ic);
      public virtual void Mark (Context ic)
        {
          throw new Exception ("Can't set predefined marker: " + name);
        }
      public virtual int CharAt (Context ic)
        {
          return ic.preedit[Position (ic)];
        }
      public override Xex.TermValue Clone () { return this; }

      public static Xex.TermValue parser (Xex.Domain domain, XmlNode node)
      {
        return Get ((MSymbol) node.InnerText);
      }

      public class Named : Marker
      {
        public Named (MSymbol name) : base (name) { }

        public override int Position (Context ic)
        {
          MPlist p = ic.markers.Find (name);
          return (p != null ? p.Integer : 0);

        }

        public override void Mark (Context ic)
        {
          ic.markers.Put (name, ic.cursor_pos);
        }
      }
     
      public class Predefined : Marker
      {
        public Predefined (MSymbol name) : base (name) { }
        
        public override int Position (Context ic)
        {
          switch (name.Name[1]) {
          case '<': return 0;
          case '>': return ic.preedit.Length;
          case '-': return ic.cursor_pos - 1;
          case '+': return ic.cursor_pos + 1;
          case '[':
            if (ic.cursor_pos > 0)
              {
                int pos = ic.cursor_pos;
                int to;
                ic.preedit.FindProp (Mcandidates, pos - 1, out pos, out to);
                return pos;
              }
            return 0;
          case ']':
            if (ic.cursor_pos < ic.preedit.Length - 1)
              {
                int pos = ic.cursor_pos;
                int from;
                ic.preedit.FindProp (Mcandidates, pos, out from, out pos);
                return pos;
              }
            return ic.preedit.Length;
          default:
            return name.Name[1] - '0';
          }
        }
      }

      public class PredefinedAbsolute : Marker
      {
        private int pos;

        public PredefinedAbsolute (MSymbol name) : base (name)
          {
            if (! int.TryParse (name.Name.Substring (1), out pos))
              throw new Exception ("Invalid marker name: " + name);
          }

        public override int Position (Context ic)
        {
          return (pos < ic.preedit.Length ? pos : ic.preedit.Length);
        }
      }

      public class PredefinedSurround : Marker
      {
        private int distance;

        public PredefinedSurround (MSymbol name) : base (name)
          {
            if (! int.TryParse (name.Name.Substring (2), out distance))
              throw new Exception ("Invalid marker name: " + name);
            if (distance > 0)
              distance--;
          }

        public override int Position (Context ic)
        {
          return ic.cursor_pos + distance;
        }

        public override int CharAt (Context ic)
          {
            int pos = ic.cursor_pos + distance;
            if (pos < 0)
              return ic.GetSurroundingChar (pos);
            else if (pos >= ic.preedit.Length)
              return ic.GetSurroundingChar (pos - ic.preedit.Length);
            return ic.preedit[pos];
          }
      }

      static internal Dictionary<MSymbol,Predefined> predefined_markers;

      static Marker ()
      {
        predefined_markers = new Dictionary<MSymbol,Predefined> ();
        MSymbol[] symlist = new MSymbol[] {"@<", "@>", "@-", "@+", "@[", "@]" };
        foreach (MSymbol s in symlist)
          predefined_markers[s] = new Predefined (s);
      }

      public static Marker Get (MSymbol name)
      {
        if (name.Name[0] == '@')
          {
            Predefined pred;
            if (predefined_markers.TryGetValue (name, out pred))
              return pred;
            if (name.Name.Length == 1)
              throw new Exception ("Invalid marker name: " + name);
            if (Char.IsDigit (name.Name[1]))
              return new PredefinedAbsolute (name);
            if (name.Name.Length == 2 || name == Mat_minus_zero
                || ! (name.Name[1] == '-' || name.Name[1] == '+'))
              throw new Exception ("Invalid marker name: " + name);
            return new PredefinedSurround (name);
          }
        return new Named (name);
      }
    }
      
    internal class Candidates
    {
      private class Block
      {
        public int Index;
        public object Data;

        public Block (int index, Xex.Term term)
        {
          Index = index;
          if (term.IsStr)
            Data = (MText) term.Strval;
          else
            {
              MPlist plist = new MPlist ();
              MPlist p = plist;
              foreach (Xex.Term t in term.Listval)
                p = p.Add (MSymbol.mtext, (MText) t.Strval);
              Data = plist;
            }
        }

        public Block (int index, MPlist plist)
        {
          Index = index;
          if (plist.IsMText)
            Data = plist.Text;
          else if (plist.IsPlist)
            Data = plist.Plist;
          else
            throw new Exception ("Invalid candidate: " + plist);
        }

        public int Count
        {
          get { return (Data is MText
                        ? ((MText) Data).Length
                        : ((MPlist) Data).Count); }
        }

        public object this[int i]
        {
          get {
            if (Data is MText) return ((MText) Data)[i];
            return  ((MPlist) Data)[i];
          }
        }
      }

      private Block[] blocks;
      private int row = 0;
      private int index = 0;
      public object[] group;

      private bool IsFixed { get { return group != null; } }
      private int Total {
        get {
          Block last = blocks[blocks.Length - 1];
          return last.Index + last.Count; }
      }

      public int Column {
        get { return (IsFixed ? index % group.Length
                      : index - blocks[row].Index); }
      }

      public object Group {
        get { return (IsFixed ? group : blocks[row].Data); }
      }

      public int GroupLength
      {
        get {
          if (IsFixed)
            {
              int nitems = group.Length;
              int start = index - (index % nitems);
              int total = Total;
              return (start + nitems <= total ? nitems : total - start);
            }
          return blocks[row].Count;
        }
      }

      public object Current {
        get {
          return (IsFixed ? group[index % group.Length]
                  : blocks[row][index - blocks[row].Index]);
        }
      }

      public Candidates (MPlist list, int column)
      {
        int nblocks = list.Count;

        blocks = new Block[nblocks];
        for (int i = 0, start = 0; i < nblocks; i++, list = list.next)
          start += (blocks[i] = new Block (index, list)).Count;
        if (column > 0)
          group = new object[column];
      }

      public Candidates (List<Xex.Term> list, int column)
      {
        int nblocks = list.Count;

        blocks = new Block[nblocks];
        for (int i = 0, start = 0; i < nblocks; i++)
          start += (blocks[i] = new Block (index, list[i])).Count;
        if (column > 0)
          group = new object[column];
      }

      public static void Detach (Context ic)
      {
        ic.preedit.PopProp (0, ic.preedit.Length, Mcandidates);
        ic.candidates = null;
        ic.changed |= (ChangedStatus.Preedit | ChangedStatus.CursorPos
                       | CandidateAll);
      }

      // Fill the array "group" by candidates stating from INDEX.
      // INDEX must be a multiple of "column".  Set NTIMES to the
      // number of valid candidates in "group".  Update "block" if
      // necessary.  Return "group".

      private int fill_group (int start)
      {
        int nitems = group.Length;
        int r = row;
        Block b = blocks[r];

        if (start < b.Index)
          while (start < b.Index)
            b = blocks[--r];
        else
          while (start >= b.Index + b.Count)
            b = blocks[++r];
        row = r;

        int count = b.Count;
        start -= b.Index;
        for (int i = 0; i < nitems; i++, start++)
          {
            if (start >= count)
              {
                r++;
                if (r == blocks.Length)
                  return i;
                b = blocks[r];
                count = b.Count;
                start = 0;
              }
            group[i] = b[start];
          }
        return nitems;
      }

      // Update "row" to what contains the first candidate of
      // the previous candidate-group, update "current_index", and
      // update "group" if necessary.  Return the previous
      // candidate-group.  Set NITEMS to the number of valid
      // candidates contained in that group.

      public int PrevGroup ()
      {
        int nitems;
        int col = Column;

        if (IsFixed)
          {
            nitems = group.Length;
            if ((index -= col + nitems) < 0)
              index = (Total / nitems) * nitems;
            nitems = fill_group (index);
          }
        else
          {
            row = row > 0 ? row-- : blocks.Length - 1;
            nitems = blocks[row].Count;
            index = blocks[row].Index;
          }
        index += col < nitems ? col : nitems - 1;
        return nitems;
      }

      public int NextGroup ()
      {
        int nitems;
        int col = Column;

        if (IsFixed)
          {
            nitems = group.Length;
            if ((index += nitems - col) >= Total)
              index = 0;
            nitems = fill_group (index);
          }
        else
          {
            row = row < blocks.Length - 1 ? row + 1 : 0;
            nitems = blocks[row].Count;
            index = blocks[row].Count;
          }
        index += col < nitems ? col : nitems - 1;
        return nitems;
      }

      public void Prev ()
      {
        int col = Column;

        if (col == 0)
          {
            int nitems = PrevGroup ();
            index += col < nitems - 1 ? col : nitems - 1;
          }
        else
          index--;
      }

      public void Next ()
      {
        int col = Column;
        int nitems = GroupLength;

        if (col == nitems - 1)
          {
            nitems = NextGroup ();
            index -= Column;
          }
        else
          index++;
      }

      public void First ()
      {
        index -= Column;
      }

      public void Last ()
      {
        index += GroupLength - (Column + 1);
      }

      public void Select (int col)
      {
        int maxcol = GroupLength - 1;
        if (col > maxcol)
          col = maxcol;
        index = index - Column + col;
      }
    }

    internal class Selector : Xex.TermValue
    {
      static new Dictionary<MSymbol, Selector> selectors;

      static Selector ()
        {
          selectors = new Dictionary<MSymbol, Selector> ();
          MSymbol[] symlist = new MSymbol[] { "@<", "@=", "@>", "@-", "@+",
                                              "@[", "@]" };
          foreach (MSymbol s in symlist)
            selectors[s] = new Selector (s);
          selectors["@first"] = new Selector ('<');
          selectors["@current"] = new Selector ('=');
          selectors["@last"] = new Selector ('>');
          selectors["@previous"] = new Selector ('-');
          selectors["@next"] = new Selector ('+');
          selectors["@previous-candidate-change"] = new Selector ('[');
          selectors["@next-candidate-change"] = new Selector (']');
        }

      private char tag;

      private Selector (MSymbol sym) { tag = sym.Name[1]; }

      private Selector (char tag) { this.tag = tag; }

      public static Xex.TermValue parser (Xex.Domain domain, XmlNode node)
      {
        return Get ((MSymbol) node.InnerText);
      }

      public static Xex.TermValue Get (MSymbol name)
      {
        Selector selector;
        if (! selectors.TryGetValue (name, out selector))
          throw new Exception ("Invalid selector name: " + name);
        return selector;
      }

      public override Xex.TermValue Clone () { return this; }

      public void Select (Candidates candidates)
      {
        switch (tag)
          {
          case '<': candidates.First (); break;
          case '>': candidates.Last (); break;
          case '-': candidates.Prev (); break;
          case '+': candidates.Next (); break;
          case '[': candidates.PrevGroup (); break;
          case ']': candidates.NextGroup (); break;
          default: break;
          }
      }
    }

    internal class Map
    {
      public MSymbol name;
      public List<Entry> entries;

      public Map (MSymbol name) { this.name = name; }

      public class Entry
      {
        public KeySeq keyseq;
        public Xex.Term[] actions;

        public Entry (Xex.Domain domain, KeySeq keyseq, Xex.Term[] actions)
        {
          this.keyseq = keyseq;
          this.actions = actions;
        }
      }
    }

    internal class Keymap
    {
      public Dictionary<Key, Keymap> submaps;
      public Xex.Term[] map_actions, branch_actions;

      public Keymap () { }

      public void Add (KeySeq keys, int index, 
                       Xex.Term[] map_actions, Xex.Term[] branch_actions)
      {
        if (index == keys.keyseq.Count)
          {
            this.map_actions = map_actions;
            this.branch_actions = branch_actions;
          }
        else
          {
            Key key = keys.keyseq[index];
            Keymap sub = null;

            if (submaps == null)
              submaps = new Dictionary<Key, Keymap> ();
            else
              submaps.TryGetValue (key, out sub);
            if (sub == null)
              submaps[key] = sub = new Keymap ();
            sub.Add (keys, index + 1, map_actions, branch_actions);
          }
      }

      public void AddMap (Map map, Xex.Term[] branch_actions)
      {
        foreach (Map.Entry entry in map.entries)
          Add (entry.keyseq, 0, entry.actions, branch_actions);
      }

      public Keymap Lookup (KeySeq keys, ref int index)
      {
        Keymap sub;

        if (index < keys.keyseq.Count
            && submaps != null
            && submaps.TryGetValue (keys.keyseq[index], out sub))
          {
            index++;
            return sub.Lookup (keys, ref index);
          }
        return this;
      }

      private void describe (MText mt, KeySeq keyseq)
      {
        if (map_actions != null || branch_actions != null)
          {
            if (mt.Length > 0)
              mt.Cat (" ");
            mt.Cat ('(').Cat (keyseq.ToString ());
            if (map_actions != null)
              foreach (Xex.Term term in map_actions)
                mt.Cat (' ').Cat (term.ToString ());
            if (branch_actions != null)
              foreach (Xex.Term term in branch_actions)
                mt.Cat (' ').Cat (term.ToString ());
            mt.Cat (')');           
          }
        if (submaps != null)
          foreach (KeyValuePair<Key, Keymap> kv in submaps)
            {
              keyseq.keyseq.Add (kv.Key);
              kv.Value.describe (mt, keyseq);
              keyseq.keyseq.RemoveAt (keyseq.keyseq.Count - 1);
            }
      }

      public override string ToString ()
      {
        MText mt = "";
        KeySeq keyseq = new KeySeq ();

        describe (mt, keyseq);
        mt.Cat (')');
        return (string) mt;
      }
    }

    internal class State
    {
      public Xex.Symbol name;
      public MText title;
      public Xex.Term[] enter_actions, fallback_actions;
      public Keymap keymap;

      public State (Xex.Symbol name, MText title)
      {
        this.name = name;
        this.title = title;
      }

      public State (MInputMethod im, XmlNode node)
      {
        this.name = node.Attributes[Qsname].Value;
        XmlAttribute attr = node.Attributes[Qtitle];
        if (attr != null)
          title = (MText) attr.Value;
        keymap = new Keymap ();
        for (node = node.FirstChild; node != null; node = node.NextSibling)
          {
            if (node.Name == Qstate_hook)
              enter_actions = Xex.ParseTerms (im.domain, node.FirstChild);
            else if (node.Name == Qcatch_all_branch)
              fallback_actions = Xex.ParseTerms (im.domain, node.FirstChild);
            else if (node.Name == Qbranch)
              {
                MSymbol mapname = node.Attributes[Qmname].Value;
                Map map;
                if (im.maps.TryGetValue (mapname, out map))
                  keymap.AddMap (map, Xex.ParseTerms (im.domain,
                                                      node.FirstChild));
                else
                  throw new Exception ("Unknown map: " + mapname);
              }
          }
      }

      public State (MInputMethod im, MPlist plist)
      {
        if (! plist.IsSymbol)
          throw new Exception ("Invalid state: " + plist);
        this.name = plist.Symbol.Name;
        plist = plist.next;
        if (plist.IsMText)
          {
            this.title = plist.Text;
            plist = plist.next;
          }
        keymap = new Keymap (); 
        for (; ! plist.IsEmpty; plist = plist.next)
          {
            if (! plist.IsPlist)
              throw new Exception ("Invalid branch: " + plist);
            MPlist p = plist.Plist;
            if (! p.IsSymbol)
              throw new Exception ("Invalid branch: " + p);
            MSymbol mapname = p.Symbol;
            if (mapname == MSymbol.t)
              enter_actions = im.parse_actions (p.next);
            else if (mapname == MSymbol.nil)
              fallback_actions = im.parse_actions (p.next);
            else
              {
                Map map;
                if (im.maps.TryGetValue (mapname, out map))
                  keymap.AddMap (map, im.parse_actions (p.next));
                else
                  throw new Exception ("Unknown map: " + mapname);
              }
            }
      }

      public override string ToString ()
      {
        MText mt = "(" + name;

        if (title != null)
          mt.Cat (" \"" + title + "\"");
        mt += keymap.ToString ();
        return (string) mt + ")";
      }
    }

    // Instance members
    internal Xex.Domain domain = new Xex.Domain (im_domain, null);

    private LoadStatus load_status = LoadStatus.None;
    private MDatabase.Tag tag;
    private MDatabase mdb;

    private MText description;
    internal MText title;
    internal Command[] commands;
    internal Xex.Symbol[] var_names;
    internal Dictionary<MSymbol, Plugin> plugins;
    internal Dictionary<MSymbol, Map> maps;
    internal Dictionary<Xex.Symbol, State> states;
    internal State initial_state;

    static MInputMethod ()
    {
      im_domain.DefTerm ("keyseq", KeySeq.parser);
      im_domain.DefTerm ("marker", Marker.parser);
      im_domain.DefTerm ("selector", Selector.parser);

      im_domain.DefSubr (Finsert, "insert", false, 1, 1);
      im_domain.DefSubr (Finsert_candidates, "candidates", false, 1, -1);
      im_domain.DefSubr (Fdelete, "delete", false, 1, 1);
      im_domain.DefSubr (Fselect, "select", false, 1, 1);
      im_domain.DefSubr (Fshow, "show", false, 0, 0);
      im_domain.DefSubr (Fhide, "hide", false, 0, 0);
      im_domain.DefSubr (Fmove, "move", false, 1, 1);
      im_domain.DefSubr (Fmark, "mark", false, 1, 1);
      im_domain.DefSubr (Fpushback, "pushback", false, 1, 1);
      im_domain.DefSubr (Fpop, "pop", false, 0, 0);
      im_domain.DefSubr (Fundo, "undo", false, 0, 1);
      im_domain.DefSubr (Fcommit, "commit", false, 0, 0);
      im_domain.DefSubr (Funhandle, "unhandle", false, 0, 0);
      im_domain.DefSubr (Fshift, "shift", false, 1, 1);
      im_domain.DefSubr (Fshiftback, "shiftback", false, 0, 0);
      im_domain.DefSubr (Fchar_at, "char-at", false, 1, 1);
      im_domain.DefSubr (Fkey_count, "key-count", false, 1, 1);
      im_domain.DefSubr (Fsurrounding_flag, "surrounding-text-flag",
                         false, 0, 0);

      MDatabase.Tag tag = new MDatabase.Tag (Minput_method, "*", "*", "*");
      List<MDatabase> list = MDatabase.List (tag);
      M17n.DebugPrint ("Found {0} input methods\n", list.Count);
      foreach (MDatabase mdb in list)
        im_table[mdb.tag] = new MInputMethod (mdb.tag);
    }

    // Constructor
    private MInputMethod (MDatabase.Tag tag)
    {
      this.tag = tag;
    }

    // Instance Properties
    public MSymbol Language { get { return tag[1]; } }
    public MSymbol Name { get { return tag[2]; } }
    public MSymbol SubName { get { return tag[3]; } }

    public bool Info (out MText description,
                      out MText title,
                      out Xex.Variable[] variables,
                      out Command[] commands)
    {
      if ((load_status & LoadStatus.Header) != LoadStatus.Header
          && ! load_header ())
        {
          description = null;
          title = null;
          variables = null;
          commands = null;
          return false;
        }
      description = this.description;
      title = this.title;
      if (var_names == null)
        variables = null;
      else
        {
          variables = new Xex.Variable[var_names.Length];
          int i = 0;
          foreach (Xex.Symbol name in var_names)
            variables[i++] = domain.GetVar (name, false);
        }
      commands = this.commands;
      return true;
    }

    public static MInputMethod Find (MSymbol language, MSymbol name)
    {
      return Find (language, name, MSymbol.nil);
    }

    public static MInputMethod Find (MSymbol language, MSymbol name,
                                     MSymbol subname)
    {
      MDatabase.Tag tag = new MDatabase.Tag (Minput_method, language,
                                             name, subname);
      MInputMethod im;

      return (im_table.TryGetValue (tag, out im) ? im : null);
    }

    public bool Open ()
    {
      return ((load_status == LoadStatus.Full) || load_body ());
    }

    public static MInputMethod[] List ()
    {
      MInputMethod[] array = new MInputMethod[im_table.Count];
      int i = 0;

      foreach (KeyValuePair<MDatabase.Tag, MInputMethod> kv in im_table)
        array[i++] = kv.Value;
      return array;
    }

    private bool load_header ()
    {
      mdb = MDatabase.Find (tag);
      if (mdb == null)
        return false;
      mdb.name_table = Xex.Symbol.Table;
      try {
        MSymbol format = mdb.Format;

        if (format == MSymbol.plist)
          load ((MPlist) mdb.Load (Mmap), false);
        else
          {
            XmlDocument doc = (XmlDocument) mdb.Load (Mmap_list);
            load (doc.DocumentElement, false);
          }
      } catch (Exception e) {
        Console.WriteLine ("{0}\n", e);
        load_status = LoadStatus.Error;
        return false;
      }
      load_status |= LoadStatus.Header;
      return true;
    }

    private bool load_body ()
    {
      mdb = MDatabase.Find (tag);
      if (mdb == null)
        return false;
      mdb.name_table = Xex.Symbol.Table;
      try {
        object obj = mdb.Load ();
        if (obj is MPlist)
          load ((MPlist) obj, true);
        else
          load ((XmlDocument) obj, true);
      } catch (Exception e) {
        Console.WriteLine (e);
        load_status = LoadStatus.Error;
        return false;
      }
      load_status = LoadStatus.Full;
      return true;
    }

    private void add_default_state ()
    {
      Xex.Symbol Qinit = "init";
      State state = new State (Qinit, null);
      foreach (KeyValuePair<MSymbol, Map>kv in maps)
        state.keymap.AddMap (kv.Value, null);
      states[Qinit] = initial_state = state;
    }

    private void load (MPlist plist, bool full)
    {
      maps = new Dictionary<MSymbol, Map> ();
      states = new Dictionary<Xex.Symbol, State> ();

      for (; ! plist.IsEmpty; plist = plist.next)
        if (plist.IsPlist)
          {
            MPlist pl = plist.Plist;
            if (pl.IsSymbol)
              {
                MSymbol sym = pl.Symbol;

                pl = pl.next;
                if (sym == Mdescription)
                  description = parse_description (pl);
                else if (sym == Mtitle)
                  {
                    if (pl.IsMText)
                      title = pl.Text;
                  }
                else if (sym == Mvariable)
                  parse_variables (pl);
                else if (sym == Mcommand)
                  parse_commands (pl);
                else if (full)
                  {
                    if (sym == Mmodule)
                      parse_plugins (pl);
                    else if (sym == Minclude)
                      parse_include (pl);
                    else if (sym == Mmacro)
                      parse_macros (pl);
                    else if (sym == Mmap)
                      parse_maps (pl);
                    else if (sym == Mstate)
                      parse_states (pl);
                  }
              }
          }
      if (description == null)
        description = (MText) "No description";
      if (title == null)
        title = new MText (tag[2].Name);
      if (commands == null)
        commands = new Command[0];
      if (! full)
        return;
      if (states.Count == 0)
        add_default_state ();
    }

    private void load (XmlNode node, bool full)
    {
      bool skip_header = load_status == LoadStatus.Header;

      maps = new Dictionary<MSymbol, Map> ();
      states = new Dictionary<Xex.Symbol, State> ();

      if (node.NodeType == XmlNodeType.Document)
        node = node.FirstChild;
      while (node.NodeType != XmlNodeType.Element)
        node = node.NextSibling;
      for (node = node.FirstChild; node != null; node = node.NextSibling)
        {
          if (node.NodeType != XmlNodeType.Element)
            continue;
          if (! skip_header)
            {
              if (node.Name == "description")
                description = parse_description (node);
              else if (node.Name == "title")
                title = parse_title (node);
              else if (node.Name == "variable-list")
                parse_variables (node);
              else if (node.Name == "command-list")
                parse_commands (node);
            }
          else if (full)
            {
              if (node.Name == "module-list")
                parse_plugins (node);
              else if (node.Name == "macro-list")
                parse_macros (node);
              else if (node.Name == "map-list")
                parse_maps (node);
              else if (node.Name == "state-list")
                parse_states (node);
            }
        }
      if (description == null)
        description = (MText) "No description";
      if (title == null)
        title = new MText (tag[2].Name);
      if (commands == null)
        commands = new Command[0];
      if (! full)
        return;
      if (states.Count == 0)
        add_default_state ();
    }

    private static void transform (MPlist plist)
    {
      for (; ! plist.IsEmpty; plist = plist.next)
        {
          if (plist.IsMText)
            {
              MPlist p = new MPlist ();
              p.Add (MSymbol.symbol, Minsert);
              p.Add (MSymbol.mtext, plist.Text);
              plist.Set (MSymbol.plist, p);
            }
          else if (plist.IsInteger)
            {
              MPlist p = new MPlist ();
              p.Add (MSymbol.symbol, Minsert);
              p.Add (MSymbol.integer, plist.Integer);
              plist.Set (MSymbol.plist, p);
            }
          else if (plist.IsPlist)
            {
              MPlist pl = plist.Plist;

              if (pl.IsSymbol)
                {
                  if (pl.Symbol == Madd)
                    pl.Set (MSymbol.symbol, (MSymbol) "+=");
                  else if (pl.Symbol == Msub)
                    pl.Set (MSymbol.symbol, (MSymbol) "-=");
                  else if (pl.Symbol == Mmul)
                    pl.Set (MSymbol.symbol, (MSymbol) "*=");
                  else if (pl.Symbol == Mdiv)
                    pl.Set (MSymbol.symbol, (MSymbol) "/=");
                  else if (pl.Symbol == Minsert)
                    {
                      // (insert (CANDIDATES ...))
                      //   => (candidates CANDIDATES ...)
                      if (pl.next.IsPlist)
                        {
                          pl.Set (MSymbol.symbol, Mcandidates);
                          pl = pl.next;
                          MPlist p = pl.Plist;
                          pl.Set (p.key, p.val);
                          for (p = p.next; ! p.IsEmpty; p = p.next);
                          pl.Add (p.key, p.val);
                        }
                    }
                  else if (pl.Symbol == Mif)
                    {
                      pl = pl.next;
                      if (! pl.IsEmpty)
                        transform (pl.next);
                    }
                  else if (pl.Symbol == Mcond)
                    {
                      for (pl = pl.next; ! pl.IsEmpty; pl = pl.next)
                        if (pl.IsPlist)
                          {
                            MPlist p = pl.Plist;

                            if (p.IsPlist)
                              transform (p);
                            else
                              transform (p.next);
                          }
                    }
                  else if (pl.Symbol == Mdelete
                           || pl.Symbol == Mmove
                           || pl.Symbol == Mmark)
                    {
                      pl = pl.next;
                      if (pl.IsSymbol)
                        {
                          MSymbol sym = pl.Symbol;
                          MPlist p = new MPlist ();
                          p.Add (MSymbol.symbol, Mmarker);
                          p.Add (MSymbol.symbol, sym);
                          pl.Set (MSymbol.plist, p);
                        }
                    }
                  else if (pl.Symbol == Mpushback)
                    {
                      pl = pl.next;
                      if (pl.IsPlist)
                        pl.Plist.Push (MSymbol.symbol, Mkeyseq);
                    }
                }
              else if (pl.IsMText)
                {
                  // (CANDIDATES ...) => (candidates CANDIDATES ...)
                  pl.Push (MSymbol.symbol, Mcandidates);
                }
            }
          else if (plist.IsSymbol)
            {
              MSymbol sym = plist.Symbol;

              if (sym.Name.Length >= 3
                  && sym.Name[0] == '@'
                  && (sym.Name[1] == '-' || sym.Name[1] == '+'))
                {
                  int pos = int.Parse (sym.Name.Substring (1));
                  MPlist p = new MPlist ();

                  if (pos == 0)
                    {
                      p.Add (MSymbol.symbol, Msurrounding_flag);
                    }
                  else
                    {
                      if (sym.Name[1] == '+')
                        pos--;
                      p.Add (MSymbol.symbol, Mchar_at);
                      p.Add (MSymbol.integer, pos);
                    }
                  plist.Set (MSymbol.plist, p);
                }
            }
        }
    }

    private static MText parse_description (MPlist plist)
    {
      if (plist.IsMText)
        return plist.Text;
      if (plist.IsPlist)
        {
          plist = plist.Plist;
          if (plist.IsSymbol && plist.Symbol == (MSymbol) "_"
              && plist.next.IsMText)
            return plist.next.Text;
        }
      return null;
    }

    private static MText parse_description (XmlNode node)
    {
      if (node.HasChildNodes)
        node = node.FirstChild;
      return node.InnerText;
    }

    private static MText parse_title (XmlNode node)
    {
      return node.InnerText;
    }

    private void new_variable (Xex.Symbol name, string desc, int val,
                               MPlist pl, Xex.Variable vari)
    {
      int[] range;

      if (pl.IsEmpty)
        range = null;
      else
        {
          range = new int[pl.Count * 2];
          for (int i = 0; i < range.Length; i++)
            {
              if (pl.IsPlist)
                {
                  MPlist p = pl.Plist;

                  if (! p.IsInteger || ! p.next.IsInteger)
                    throw new Exception ("Invalid range: " + p);
                  range[i * 2] = p.Integer;
                  range[i * 2 + 1] = p.next.Integer;
                }
              else if (pl.IsInteger)
                range[i * 2] = range[i * 2 + 1] = pl.Integer;
              else
                throw new Exception ("Invalid range: " + pl);
            }
        }
      if (vari == null)
        domain.Defvar (new Xex.Variable.Int (name, desc, val, range));
      else
        {
          Xex.Term term = new Xex.Term (val);
          vari.Value = term;
          vari.DefaultValue = term;
          vari.Range = range;
        }
    }

    private void new_variable (Xex.Symbol name, string desc, MText val,
                               MPlist pl, Xex.Variable vari)
    {
      string[] range;

      if (pl.IsEmpty)
        range = null;
      else
        {
          range = new string[pl.Count * 2];
          for (int i = 0; i < range.Length; i++)
            {
              if (pl.IsMText)
                range[i] = (string) pl.Text;
              else
                throw new Exception ("Invalid range: " + pl);
            }
        }
      if (vari == null)
        domain.Defvar (new Xex.Variable.Str (name, desc, (string) val, range));
      else
        {
          Xex.Term term = new Xex.Term ((string) val);
          vari.Value = term;
          vari.DefaultValue = term;
          vari.Range = range;
        }
    }

    private void new_variable (Xex.Symbol name, string desc, MSymbol val,
                               MPlist pl, Xex.Variable vari)
    {
      Xex.Symbol[] range;
      Xex.Symbol sym = val.Name;

      if (pl.IsEmpty)
        range = null;
      else
        {
          range = new Xex.Symbol[pl.Count * 2];
          for (int i = 0; i < range.Length; i++)
            {
              if (pl.IsSymbol)
                range[i] = pl.Symbol.Name;
              else
                throw new Exception ("Invalid range: " + pl);
            }
        }
      if (vari == null)
        domain.Defvar (new Xex.Variable.Sym (name, desc, sym, range));
      else
        {
          Xex.Term term = new Xex.Term (sym);
          vari.Value = term;
          vari.DefaultValue = term;
          vari.Range = range;
        }
    }

    private Xex.Variable get_global_var (Xex.Symbol name)
    {
      if (im_global == null || this != im_global)
        {
          tag = new MDatabase.Tag (Minput_method, MSymbol.t, MSymbol.nil,
                                   "global");
          im_global = im_table[tag];
          if (! im_global.Open ())
            throw new Exception ("Failed to load global"); 
        }
      return im_global.domain.GetVar (name, false);
    }

    private void parse_variables (MPlist plist)
    {
      var_names = new Xex.Symbol[plist.Count];

      for (int i = 0; ! plist.IsEmpty; i++, plist = plist.next)
        {
          if (! plist.IsPlist || ! plist.Plist.IsSymbol)
            throw new Exception ("Invalid variable: " + plist);

          MPlist p = plist.Plist;
          Xex.Symbol name = (Xex.Symbol) p.Symbol.Name;
          var_names[i] = name;
          p = p.next;
          string desc = (string) parse_description (p);
          Xex.Variable vari = get_global_var (name);
          if (vari != null)
            domain.Defvar (vari);
          if (desc != null)
            p = p.next;
          if (! p.IsEmpty)
            {
              if (p.IsInteger)
                new_variable (name, desc, p.Integer, p.next, vari);
              else if (p.IsMText)
                new_variable (name, desc, p.Text, p.next, vari);
              else if (p.IsSymbol)
                new_variable (name, desc, p.Symbol, p.next, vari);
              else
                throw new Exception ("Invalid variable type: " + p.val);
            }
        }
    }

    private void parse_variables (XmlNode node)
    {
      XmlNodeList node_list = node.ChildNodes;

      var_names = new Xex.Symbol[node_list.Count];
      for (int i = 0; i < node_list.Count; i++)
        {
          Xex.Symbol name = node_list[i].Attributes[0].Value;
          Xex.Variable vari = get_global_var (name);
          if (vari != null)
            domain.Defvar (vari);
          domain.Defvar (node_list[i]);
          var_names[i] = name;
        }
    }

    private void parse_commands (MPlist plist)
    {
      commands = new Command[plist.Count];

      for (int i = 0; ! plist.IsEmpty; plist = plist.next)
        if (plist.IsPlist && plist.Plist.IsSymbol)
          commands[i++] = new Command (plist.Plist);
    }

    private void parse_commands (XmlNode node)
    {
      XmlNodeList node_list = node.ChildNodes;

      commands = new Command[node_list.Count];
      for (int i = 0; i < node_list.Count; i++)
        {
          if (node_list[i].NodeType == XmlNodeType.Element)
            commands[i] = new Command (node_list[i]);
        }
    }

    private void parse_plugins (MPlist plist)
    {
      plugins = new Dictionary<MSymbol, Plugin> ();

      for (; ! plist.IsEmpty; plist = plist.Next)
        {
          MPlist p = plist.Plist;
          MSymbol sym = p.Symbol;
          Plugin plugin = new Plugin (sym.Name);

          for (p = p.next; ! p.IsEmpty; p = p.next)
            {
              Xex.Function func = new PluginMethod (plugin, p.Symbol.Name);
              domain.Defun (func);
            }
        }
    }

    private void parse_plugins (XmlNode node)
    {
      plugins = new Dictionary<MSymbol, Plugin> ();

      foreach (XmlNode n in node.ChildNodes)
        {
          Plugin plugin = new Plugin (n.Attributes[0].Value);
          foreach (XmlNode nn in n.ChildNodes)
            {
              Xex.Function func = new PluginMethod (plugin,
                                                    nn.Attributes[0].Value);
              domain.Defun (func);
            }
        }
    }

    private void parse_macros (XmlNode node)
    {
      for (XmlNode nn = node.FirstChild; nn != null; nn = nn.NextSibling)
        if (nn.NodeType == XmlNodeType.Element)
          domain.Defun (nn, true);
      for (XmlNode nn = node.FirstChild; nn != null; nn = nn.NextSibling)
        if (nn.NodeType == XmlNodeType.Element)
          domain.Defun (nn, false);
    }

    private void parse_maps (XmlNode node)
    {
      for (node = node.FirstChild; node != null; node = node.NextSibling)
        if (node.Name == Qmap)
          {
            MSymbol name = node.Attributes[0].Value;
            Map map = new Map (name);
            maps[name] = map;
            for (XmlNode nd = node.FirstChild; nd != null; nd = nd.NextSibling)
              if (nd.Name == Qrule)
                {
                  XmlNode n = nd.FirstChild;
                  if (n.Name != Qkeyseq)
                    continue;
                  KeySeq keyseq = (KeySeq) KeySeq.parser (domain, n);
                  Xex.Term[] actions = Xex.ParseTerms (domain, n.NextSibling);
                  map.entries.Add (new Map.Entry (domain, keyseq, actions));
                }
          }
    }

    private void parse_states (MPlist plist)
    {
      for (; ! plist.IsEmpty; plist = plist.next)
        if (plist.IsPlist)
          {
            State state = new State (this, plist.Plist);
            states[state.name] = state;     
          }
    }

    private void parse_states (XmlNode node)
    {
      for (node = node.FirstChild; node != null; node = node.NextSibling)
        if (node.Name == Qstate)
          {
            State state = new State (this, node);
            states[state.name] = state;
          }
    }

    private void parse_include (MPlist plist)
    {
      if (! plist.IsPlist)
        return;
      MPlist p = plist.Plist;
      MSymbol language, name, subname;
      language = p.Symbol;
      p = p.next;
      if (! p.IsSymbol)
        name = subname = MSymbol.nil;
      else
        {
          name = p.Symbol;
          p = p.next;
          if (! p.IsSymbol)
            subname = MSymbol.nil;
          else
            subname = p.Symbol;
        }

      MInputMethod im = MInputMethod.Find (language, name, subname);
      if (im == null)
        return;
      if (! im.Open ())
        return;
      plist = plist.next;
      if (! plist.IsSymbol)
        return;
      MSymbol target_type = plist.Symbol;
      plist = plist.next;
      MSymbol target_name = MSymbol.nil;
      if (plist.IsSymbol)
        target_name = plist.Symbol;
      if (target_type == Mmacro)
        {
          if (target_name == MSymbol.nil)
            im.domain.CopyFunc (domain);
          else
            im.domain.CopyFunc (domain, (Xex.Symbol) target_name.Name);
        }
      else if (target_type == Mmap)
        {
          if (target_name == MSymbol.nil)
            {
              foreach (KeyValuePair<MSymbol, Map> kv in im.maps)
                maps[kv.Key] = kv.Value;
            }
          else
            {
              Map map;
              if (im.maps.TryGetValue (target_name, out map))
                maps[target_name] = map;
            }
        }
      else if (target_type == Mstate)
        {
          if (target_name == MSymbol.nil)
            {
              foreach (KeyValuePair<Xex.Symbol, State> kv in im.states)
                states[kv.Key] = kv.Value;
            }
          else
            {
              Xex.Symbol state_name = target_name.Name;
              State state;
              if (im.states.TryGetValue (state_name, out state))
                states[state_name] = state;
            }
        }
    }

    private Xex.Term parse_cond (MPlist plist)
    {
      Xex.Term[] args = new Xex.Term[plist.Count];

      for (int i = 0; ! plist.IsEmpty; i++, plist = plist.next)
        {
          if (! plist.IsPlist)
            throw new Exception ("Invalid cond args: " + plist);
          MPlist p = plist.Plist;
          List<Xex.Term> arg = new List<Xex.Term> (parse_actions (p));
          args[i] = new Xex.Term (arg);
        }
      return new Xex.Term (domain, (Xex.Symbol) Mcond.Name, args);
    }

    private Xex.Term parse_insert (MPlist plist)
    {
      Xex.Term[] args;
      Xex.Term arg;
      if (plist.IsSymbol)
        arg = new Xex.Term (domain, (Xex.Symbol) plist.Symbol.Name);
      else if (plist.IsMText)
        arg = new Xex.Term ((string) plist.Text);
      else if (plist.IsInteger)
        arg = new Xex.Term (plist.Integer);
      else if (plist.IsPlist)
        {
          MPlist pl = plist.Plist;
          args = new Xex.Term[pl.Count];
          int i;
          for (i = 0; ! pl.IsEmpty; i++, pl = pl.next)
            {
              if (pl.IsMText)
                args[i] = new Xex.Term ((string) pl.Text);
              else if (pl.IsPlist)
                {
                  List<Xex.Term> list = new List<Xex.Term> ();
                  for (MPlist p = pl.Plist; ! p.IsEmpty; p = p.next)
                    {
                      if (p.IsMText)
                        list.Add (new Xex.Term ((string) p.Text));
                      else
                        throw new Exception ("Invalid candidates: " + p);
                    }                 
                }
              else
                throw new Exception ("Invalid candidates: " + pl);
            }
          return new Xex.Term (domain, Qinsert_candidates, args);
        }
      else
        throw new Exception ("Invalid arg to insert: " + plist);
      args = new Xex.Term[1];
      args[0] = arg;
      return new Xex.Term (domain, Qinsert, args);
    }

    private Xex.Term parse_select (MPlist plist)
    {
      Xex.Term[] args = new Xex.Term[1];
      if (plist.IsInteger)
        args[0] = new Xex.Term (plist.Integer);
      else if (! plist.IsSymbol)
        throw new Exception ("Invalid arg to select: " + plist);
      else if (plist.Symbol.Name[0] == '@')
        args[0] = new Xex.Term (Selector.Get (plist.Symbol));
      else
        args[0] = new Xex.Term (domain, (Xex.Symbol) plist.Symbol.Name);
      return new Xex.Term (domain, (Xex.Symbol) Mselect.Name, args);
    }

    private Xex.Term parse_funcall_with_marker (MPlist plist, MSymbol func)
    {
      Xex.Term[] args = new Xex.Term[1];
      if (plist.IsInteger && func != Mmark)
        args[0] = new Xex.Term (plist.Integer);
      else if (plist.IsSymbol)
        args[0] = new Xex.Term (Marker.Get (plist.Symbol));
      else
        throw new Exception ("Invalid arg to " + func + ": " + plist);
      return new Xex.Term (domain, (Xex.Symbol) func.Name, args);
    }

    private Xex.Term parse_char_at (MSymbol name)
    {
      Xex.Term[] args = new Xex.Term[1];
      args[0] = new Xex.Term (Marker.Get (name));
      return new Xex.Term (domain, Qchar_at, args);
    }

    private Xex.Term parse_action (MPlist plist)
    {
      if (plist.IsPlist)
        {
          MPlist p = plist.Plist;
              
          if (p.IsMText || p.IsPlist)
            return parse_insert (p);
          if (! p.IsSymbol)
            throw new Exception ("Invalid action: " + p);
          MSymbol name = p.Symbol;
          p = p.next;
          if (name == Mcond)
            return parse_cond (p);
          if (name == Minsert)
            return parse_insert (p);
          if (name == Mselect)
            return parse_select (p);
          if (name == Mdelete || name == Mmove || name == Mmark)
            return parse_funcall_with_marker (p, name);
          if (name.Name[0] == '@')
            return parse_char_at (name);
          if (name == Mset || name == Madd || name == Msub
                   || name == Mmul || name == Mdiv)
            {
              if (! p.IsSymbol)
                throw new Exception ("Invalid action: " + p);
              Xex.Symbol varname = p.Symbol.Name;
              return new Xex.Term (domain, (Xex.Symbol) name.Name,
                                   varname, parse_actions (p.next));
            }
          else
            return new Xex.Term (domain, (Xex.Symbol) name.Name,
                                 parse_actions (p));
        }
      else if (plist.IsMText || plist.IsInteger || plist.IsSymbol)
        return parse_insert (plist);
      else
        throw new Exception ("Invalid action: " + plist);
    }

    private Xex.Term[] parse_actions (MPlist plist)
    {
      Xex.Term[] terms = new Xex.Term[plist.Count];

      for (int i = 0; ! plist.IsEmpty; i++, plist = plist.next)
        terms[i] = parse_action (plist);
      return terms;
    }

    private void parse_macros (MPlist plist)
    {
      for (MPlist pl = plist; ! pl.IsEmpty; pl = pl.next)
        if (pl.IsPlist)
          {
            MPlist p = pl.Plist;

            if (! p.IsSymbol)
              continue;
            domain.Defun ((Xex.Symbol) p.Symbol.Name, false, null, null, true);
          }
      for (MPlist pl = plist; ! pl.IsEmpty; pl = pl.next)
        if (pl.IsPlist)
          {
            MPlist p = pl.Plist;

            if (! p.IsSymbol)
              continue;
            transform (p.next);
            domain.Defun ((Xex.Symbol) p.Symbol.Name, false, null,
                          parse_actions (p.next), false);
          }
    }

    private void parse_maps (MPlist plist)
    {
      for (; ! plist.IsEmpty; plist = plist.next)
        if (plist.IsPlist)
          {
            MPlist pl = plist.Plist;
          
            if (! pl.IsSymbol)
              continue;
            Map map = new Map (pl.Symbol);
            maps[pl.Symbol] = map;
            for (pl = pl.next; ! pl.IsEmpty; pl = pl.next)
              {
                if (! pl.IsPlist)
                  continue;
                MPlist p = pl.Plist;
                KeySeq keys;
                if (p.IsMText)
                  keys = new KeySeq (p.Text);
                else if (p.IsPlist)
                  keys = new KeySeq (p.Plist);
                else
                  continue;
                p = p.next;
                if (p.IsEmpty)
                  continue;
                Xex.Term[] actions = parse_actions (p);
                map.entries.Add (new Map.Entry (domain, keys, actions));
              }
          }
    }

    private static Xex.Term Finsert (Xex.Domain domain, Xex.Variable vari,
                                     Xex.Term[] args)
    {
      ((Context) domain.context).insert (args[0]);
      return args[0];
    }

    private static Xex.Term Finsert_candidates (Xex.Domain domain,
                                                Xex.Variable vari,
                                                Xex.Term[] args)
    {
      ((Context) domain.context).insert_candidates (args[0]);
      return args[0];
    }

    private static Xex.Term Fchar_at (Xex.Domain domain, Xex.Variable vari,
                                      Xex.Term[] args)
    {
      Context ic = (Context) domain.context;
      Marker m = (Marker) args[0].Objval;

      return new Xex.Term (ic.char_at (m.Position (ic)));
    }

    private static Xex.Term Fdelete (Xex.Domain domain, Xex.Variable vari,
                                   Xex.Term[] args)
    {
      ((Context) domain.context).delete ((int) args[0].Intval);
      return args[0];
    }

    private static Xex.Term Fselect (Xex.Domain domain, Xex.Variable vari,
                                     Xex.Term[] args)
    {
      Candidates can = ((Context) domain.context).candidates;

      if (can != null)
        ((Selector) args[0].Objval).Select (can);
      return args[0];
    }

    private static Xex.Term Fshow (Xex.Domain domain, Xex.Variable vari,
                                 Xex.Term[] args)
    {
      ((Context) domain.context).show ();
      return Tnil;
    }

    private static Xex.Term Fhide (Xex.Domain domain, Xex.Variable vari,
                                 Xex.Term[] args)
    {
      ((Context) domain.context).hide ();
      return Tnil;
    }

    private static Xex.Term Fmove (Xex.Domain domain, Xex.Variable vari,
                                 Xex.Term[] args)
    {
      if (args[0].IsInt)
        ((Context) domain.context).move (args[0].Intval);
      else
        {
          Marker m = (Marker) args[0].Objval;
          Context ic = (Context) domain.context;
          ((Context) domain.context).move (m.Position (ic));
        }
      return args[0];
    }

    private static Xex.Term Fmark (Xex.Domain domain, Xex.Variable vari,
                                   Xex.Term[] args)
    {
      Marker m = (Marker) args[0].Objval;
      m.Mark ((Context) domain.context);
      return args[0];
    }

    private static Xex.Term Fpushback (Xex.Domain domain, Xex.Variable vari,
                                       Xex.Term[] args)
    {
      Context ic = (Context) domain.context;

      if (args[0].IsInt)
        ic.pushback (args[0].Intval);
      else if (args[0].IsStr)
        ic.pushback (new KeySeq (args[0].Strval));
      else
        ic.pushback ((KeySeq) args[0].Objval);
      return args[0];
    }

    private static Xex.Term Fpop (Xex.Domain domain, Xex.Variable vari,
                                  Xex.Term[] args)
    {
      ((Context) domain.context).pop ();
      return Tnil;
    }

    private static Xex.Term Fundo (Xex.Domain domain, Xex.Variable vari,
                                   Xex.Term[] args)
    {
      int n = args.Length == 0 ? -2 : args[0].Intval;
      ((Context) domain.context).undo (n);
      return Tnil;
    }

    private static Xex.Term Fcommit (Xex.Domain domain, Xex.Variable vari,
                                     Xex.Term[] args)
    {
      ((Context) domain.context).commit ();
      return Tnil;
    }

    private static Xex.Term Funhandle (Xex.Domain domain, Xex.Variable vari,
                                       Xex.Term[] args)
    {
      ((Context) domain.context).commit ();
      args = new Xex.Term[2];
      args[0] = args[1] = Tcatch_tag;
      return Xex.Fthrow (domain, vari, args);
    }

    private static Xex.Term Fshift (Xex.Domain domain, Xex.Variable vari,
                                    Xex.Term[] args)
    {
      ((Context) domain.context).shift (args[0].Symval);
      return args[0];
    }

    private static Xex.Term Fshiftback (Xex.Domain domain, Xex.Variable vari,
                                        Xex.Term[] args)
    {
      ((Context) domain.context).shiftback ();
      return Tnil;
    }

    private static Xex.Term Fkey_count (Xex.Domain domain, Xex.Variable vari,
                                        Xex.Term[] args)
    {
      return new Xex.Term (((Context) domain.context).key_head);
    }

    private static Xex.Term Fsurrounding_flag (Xex.Domain domain,
                                               Xex.Variable vari,
                                               Xex.Term[] args)
    {
      return new Xex.Term (((Context) domain.context).SurroundingFlag);
    }

    public override string ToString ()
    {
      string str = (String.Format ("({0} (title \"{1}\")", tag, title));
      if (commands != null)
        {
          str += " (commands";
          foreach (Command cmd in commands)
            str += " " + cmd;
          str += ")";
        }
      if (var_names != null)
        {
          str += " (variables";
          foreach (Xex.Symbol var in var_names)
            str += " " + var;
          str += ")";
        }
      if (plugins != null)
        {
          str += " (modules";
          foreach (KeyValuePair<MSymbol, Plugin> kv in plugins)
            str += " " + kv.Value;
          str += ")";
        }
      str += " (maps";
      foreach (KeyValuePair<MSymbol, Map> kv in maps)
        str += " " + kv.Value;
      str += ") (states";
      foreach (Xex.Symbol name in states.Keys)
        str += " " + name;
      return str + "))";
    }

    public class Context
    {
      internal static Xex.Symbol Qcandidates_group_size
        = "candidates-group-size";
      private MInputMethod im;
      private Dictionary<MSymbol, Callback> callbacks
        = new Dictionary<MSymbol, Callback> ();

      private MText produced;
      private bool active;
      private MText status;
      internal MText preedit;
      internal int cursor_pos;
      internal MPlist markers;
      internal Candidates candidates;
      private int candidate_from, candidate_to;
      private bool candidate_show;

      private List<State> state_list = new List<State> state_list ();
      private Keymap keymap;

      // Sequence of input keys.
      internal KeySeq keys = new KeySeq ();

      // Index into KEYS specifying the next key to handle.
      internal int key_head;


      private int state_key_head;
      private object state_var_values;
      private int commit_key_head;
      private MText state_preedit;
      private int state_pos;
      internal MText preceding_text = new MText ();
      internal MText following_text = new MText ();

      // Set to false before calling the method 'handle_key', and set
      // to true when some key is unhandled.
      private bool key_unhandled;

      // The unhandled key.  It has the meaning only when
      // 'key_unhandled' is true.
      private Key unhandled_key;

      internal Xex.Domain domain;

      internal ChangedStatus changed;

      static MPlist callback_arg = new MPlist ();

      private bool call_callback (MSymbol name, MPlist arg)
      {
        Callback callback;
        if (! callbacks.TryGetValue (name, out callback))
          return false;
        return callback (this, arg);
      }

      private bool get_surrounding_text (int len)
      {
        if (len < 0 ? -len <= preceding_text.Length
            : len <= following_text.Length)
          return true;
        callback_arg.Set (MSymbol.integer, len);
        if (! call_callback (Mget_surrounding_text, callback_arg)
            || ! callback_arg.IsMText)
          return false;
        if (len < 0)
          {
            preceding_text = callback_arg.Text;
            return (-len <= preceding_text.Length);
          }
        following_text = callback_arg.Text;
        return (len <= following_text.Length);
      }

      internal int SurroundingFlag
      {
        get { return (callbacks.ContainsKey (Mget_surrounding_text) ? 1 : 0); }
      }

      internal int GetSurroundingChar (int pos)
      {
        if (! get_surrounding_text (pos < 0 ? pos : pos + 1))
          return 0;
        if (pos < 0)
          return preceding_text[preceding_text.Length + pos];
        return following_text[pos];
      } 

      private void adjust_markers (int from, int to, object inserted)
      {
        int ins = (inserted == null ? 0
                   : inserted is int ? 1
                   : ((MText) inserted).Length);
        int diff = ins - (to - from);

        for (MPlist plist = markers; ! plist.IsEmpty; plist = plist.next)
          {
            int pos = plist.Integer;
            if (pos > from)
              {
                if (pos >= to)
                  plist.val = pos + diff;
                else
                  plist.val = from;
              }
          }
        if (cursor_pos >= to)
          cursor_pos += diff;
        else if (cursor_pos > from)
          cursor_pos = from;
      }

      private void preedit_replace (int from, int to, int c)
      {
        preedit.Del (from, to);
        preedit.Ins (from, c);
        adjust_markers (from, to, c);
      }

      private void preedit_replace (int from, int to, MText mt)
      {
        preedit[from, to] = mt;
        adjust_markers (from, to, mt);
      }

      internal void insert (Xex.Term arg)
      {
        if (arg.IsInt)
          preedit_replace (cursor_pos, cursor_pos, arg.Intval);
        else
          preedit_replace (cursor_pos, cursor_pos, new MText (arg.Strval));
        changed |= ChangedStatus.Preedit | ChangedStatus.CursorPos;
      }

      private void update_candidate ()
      {
        object candidate = candidates.Current;

        if (candidate is MText)
          {
            preedit_replace (candidate_from, candidate_to, (MText) candidate);
            candidate_to = candidate_from + ((MText) candidate).Length;
          }
        else
          {
            preedit_replace (candidate_from, candidate_to, (int) candidate);
            candidate_to = candidate_from + 1;
          }
        preedit.PushProp (candidate_from, candidate_to,
                          Mcandidates, this);
        cursor_pos = candidate_from;
        changed |= (ChangedStatus.Preedit | ChangedStatus.CursorPos
                    | CandidateAll);
      }

      internal void insert_candidates (Xex.Term arg)
      {
        int column = 0;
        Xex.Variable v = domain.GetVar (Qcandidates_group_size, false);

        if (v != null)
          column = v.Value.Intval;
        candidates = new Candidates (arg.Listval, column);
        candidate_from = candidate_to = cursor_pos;
        update_candidate ();
      }

      internal void select (int n)
      {
        if (candidates != null)
          {
            candidates.Select (n);
            update_candidate ();
          }
      }

      internal int marker (MSymbol sym)
      {
        int pos = cursor_pos;

        if (sym.Name.Length == 2 && sym.Name[0] == '@')
          {
            switch (sym.Name[0])
              {
              case '<': pos = 0; break;
              case '>': pos = preedit.Length; break;
              case '-': pos = cursor_pos - 1; break;
              case '+': pos = cursor_pos + 1; break;
              case '[':
                if (pos > 0)
                  {
                    int to;
                    preedit.FindProp (Mcandidates, pos - 1,
                                      out pos, out to);
                  }
                else
                  pos = 0;
                break;
              case ']':
                if (cursor_pos < preedit.Length - 1)
                  {
                    int from;
                    preedit.FindProp (Mcandidates, pos,
                                      out from, out pos);
                  }
                else
                  pos = preedit.Length;
                break;
              default:
                if (sym.Name[0] >= '0' && sym.Name[0] <= '9')
                  pos = sym.Name[0];
                break;
              }
          }
        else if (sym.Name.Length >= 3 && sym.Name[0] == '@')
          {
            pos = int.Parse (sym.Name.Substring (2));
          }
        else
          {
            object val = markers.Get (sym);

            if (val is int)
              pos = (int) val;
          }
        return pos;
      }

      internal int char_at (int pos)
      {
        int c;

        pos += cursor_pos;
        if (pos < 0)
          {
            if (preceding_text.Length < -pos)
              {
                MPlist plist = new MPlist ();
                plist.Push (MSymbol.integer, pos);
                if (GetSurroundingText != null
                    && GetSurroundingText (this, plist)
                    && plist.IsMText
                    && preceding_text.Length < plist.Text.Length)
                  preceding_text = plist.Text;
              }
            c = (-pos < preceding_text.Length
                 ? preceding_text[preceding_text.Length + pos] : -1);
          }
        else if (pos >= 0 && pos < preedit.Length)
          c = preedit[pos];
        else
          {
            pos -= preedit.Length;
            if (pos >= following_text.Length)
              {
                MPlist plist = new MPlist ();
                plist.Push (MSymbol.integer, pos + 1);
                if (GetSurroundingText != null
                    && GetSurroundingText (this, plist)
                    && plist.IsMText
                    && following_text.Length < plist.Text.Length)
                  following_text = plist.Text;
              }
            c = (pos < following_text.Length ? following_text[pos] : -1);
          }
        return c;
      }

      internal void delete (int pos)
      {
        if (pos < cursor_pos)
          preedit_replace (pos, cursor_pos, null);
        else
          preedit_replace (cursor_pos, pos, null);
        changed |= ChangedStatus.Preedit | ChangedStatus.CursorPos;
      }

      internal void show ()
      {
        candidate_show = true;
        changed |= ChangedStatus.CandidateShow;
      }

      internal void hide ()
      {
        candidate_show = false;
        changed |= ChangedStatus.CandidateShow;
      }

      internal void move (int pos)
      {
        if (pos < 0)
          pos = 0;
        else if (pos > preedit.Length)
          pos = preedit.Length;
        if (pos != cursor_pos)
          {
            cursor_pos = pos;
            changed |= ChangedStatus.Preedit;
          }
      }

      internal void pushback (int n)
      {
        if (n > 0)
          {
            key_head -= n;
            if (key_head < 0)
              key_head = 0;
          }
        else if (n == 0)
          key_head = 0;
        else
          {
            key_head = - n;
            if (key_head > keys.keyseq.Count)
              key_head = keys.keyseq.Count;
          }
      }

      internal void pushback (KeySeq keyseq)
      {
        if (key_head > 0)
          key_head--;
        if (key_head < keys.keyseq.Count)
          keys.keyseq.RemoveRange (key_head, keys.keyseq.Count - key_head);
        for (int i = 0; i < keyseq.keyseq.Count; i++)
          keys.keyseq.Add (keyseq.keyseq[i]);
      }

      internal void pop ()
      {
        if (key_head < keys.keyseq.Count)
          keys.keyseq.RemoveRange (key_head, 1);
      }

      internal void undo (int n)
      {
        if (n < 0)
          keys.keyseq.RemoveRange (keys.keyseq.Count + n, - n);
        else
          keys.keyseq.RemoveRange (n, keys.keyseq.Count  - n);
        reset ();
      }

      internal void commit ()
      {
        produced.Cat (preedit);
        preedit.Del ();
        changed |= ChangedStatus.Preedit;
      }

      private void new_state (bool changed)
      {
        if (state_list.Count == 1)
          {
            commit ();
            reset ();
          }
        else
          {
            state_key_head = key_head;
            state_pos = cursor_pos;
            state_preedit = preedit.Dup ();
            state_var_values = domain.SaveValues ();
            if (changed)
              {
                State state = state_list[state_list.Count - 1];
                status = state.title;
                if (status == null)
                  status = im.title;
                this.changed |= ChangedStatus.StateTitle;
                if (state.enter_actions != null)
                  on_entry.Eval (domain);
              }
          }
      }

      internal void shift (Xex.Symbol sym)
      {
        State state;
        bool changed;

        if (! im.states.TryGetValue (sym, out state))
          throw new Exception ("Unknown state: " + sym);
        changed = state != state_list[state_list.Count - 1];
        if (changed)
          state_list.Add (state);
        new_state (changed);
      }

      internal void shiftback ()
      {
        if (state_list.Count > 1)
          state_list.RemoveAt (state_list.Count - 1);
        new_state (true);
      }

      internal void reset ()
      {
        preedit.Del ();
        state_preedit.Del ();
        produced.Del ();
        markers.Clear ();
        cursor_pos = 0;
        keys.keyseq.Clear ();
        key_head = commit_key_head = 0;
        state_list.Clear ();
        state_list.Add (im.initial_state);
        keymap = im.initial_state.keymap;
        key_head = state_key_head = 0;
        state_pos = 0;
      }

      public Context (MInputMethod im)
      {
        this.im = im;
        domain = new Xex.Domain (im.domain, this);
        reset ();
      }

      public ChangedStatus Changed { get { return changed; } }

      public void AddCallback (MSymbol name, Callback callback)
      {
        callbacks[name] = callback;
      }

      internal object GetCandidates (out int column)
      {
        column = 0;
        if (cursor_pos == 0)
          return null;
        Candidates candidates
          = (Candidates) preedit.GetProp (cursor_pos - 1, Mcandidates);
        if (candidates == null)
          return null;
        column = candidates.Column;
        return candidates.Current;
      }

      private bool handle_key ()
      {
        State state = state_list[state_list.Count - 1];
        Keymap sub = keymap.Lookup (keys, ref key_head);

        if (sub != keymap)
          {
            keymap = sub;
            if (keymap->map_actions)
              {
                restore_state ();
                if (! take_action (keymap->map_actions))
                  return false;
              }
            else if (keymap->submaps != null)
              {
                for (int i = state_key_head; i < n; i++)
                  preedit_replace (cursor_pos, cursor_pos,
                                   keys.keyseq[i].ToChar ());
              }

            if (keymap->submaps == null)
              {
                if (keymap->branch_actions != null)
                  {
                    if (! take_action (keymap->branch_actions))
                      return false;
                  }
                if (keymap != state->keymap)
                  shift (state->name);
              }
          }
        else
          {
            if (keymap->branch_actions)
              {
                if (! take_action (keymap->branch_actions))
                  return false;
              }
            
          }
      }

      public bool Toggle ()
      {
        active = ! active;
        return active;
      }

      public bool UnhandledKey (out Key key)
      {
        key = unhandled_key;
        return key_unhandled;
      }

      public bool Produced (out MText mt)
      {
        mt = produced;
        return (produced.Length > 0);
      }

      // Return value:
      //   true: All keys are handled and there's no text to commit.
      //   false: Some key is unhandled or there's a text to commit.
      //      The caller should use methods UnhandledKey and Produced.

      public bool Filter (Key key)
      {
        if (key == Key.Reload)
          return true;
        changed = ChangedStatus.None;
        produced.Del ();
        preceding_text.Del ();
        following_text.Del ();

        key_unhandled = false;
        keys.keyseq.Add (key);
        int count = 0;
        while (key_head < keys.keyseq.Count)
          {
            if (! handle_key ())
              {
                unhandled_key = keys.keyseq[key_head++];
                key_unhandled = true;
                break;
              }
            if (++count == 100)
              break;
          }
        keys.keyseq.RemoveRange (0, key_head);
        return (! key_unhandled && produced.Length == 0);
      }
    }
  }
}