XmlExpr.cs

   1 using System;
   2 using System.Collections;
   3 using System.Collections.Generic;
   4 using System.IO;
   5 using System.Xml;
   6
   7 namespace System.Xml.Expression
   8 {
   9   public abstract class Xex
  10   {
  11     public struct Name : IEquatable<Name>
  12     {
  13       private static NameTable nt = new NameTable ();
  14
  15       private string name;
  16
  17       public Name (string str)
  18         {
  19           name = nt.Add (str);
  20         }
  21
  22       public static implicit operator Name (string str)
  23       {
  24         return new Name (str);
  25       }
  26
  27       public static implicit operator string (Name name)
  28       {
  29         return name.name;
  30       }
  31
  32       public static bool operator== (Name n1, Name n2)
  33         {
  34           return (object) n1.name == (object) n2.name;
  35         }
  36
  37       public static bool operator!= (Name n1, Name n2)
  38         {
  39           return (object) n1.name != (object) n2.name;
  40         }
  41
  42       public static bool operator== (Name n1, string n2)
  43         {
  44           return (object) n1.name == (object) n2;
  45         }
  46
  47       public static bool operator!= (Name n1, string n2)
  48         {
  49           return (object) n1.name != (object) n2;
  50         }
  51
  52       public static bool operator== (string n1, Name n2)
  53         {
  54           return (object) n1 == (object) n2.name;
  55         }
  56
  57       public static bool operator!= (string n1, Name n2)
  58         {
  59           return (object) n1 != (object) n2.name;
  60         }
  61
  62       public bool Equals (Name name)
  63       {
  64         return Object.ReferenceEquals (this.name, name.name);
  65       }
  66
  67       public override bool Equals (object obj)
  68       {
  69         return Object.ReferenceEquals (this.name, obj);
  70       }
  71
  72       public override int GetHashCode ()
  73       {
  74         return name.GetHashCode ();
  75       }
  76
  77       public static NameTable Table { get { return nt; } }
  78
  79       public override string ToString () { return name; }
  80     }
  81
  82     private static Name Nexpr = "expr";
  83
  84     private static Name Nfuncall = "funcall";
  85     private static Name Nvariable = "variable";
  86     private static Name Ninteger = "integer";
  87     private static Name Nstring = "string";
  88     private static Name Nboolean = "boolean";
  89     private static Name Nsymbol = "symbol";
  90     private static Name Nlist = "list";
  91     private static Name Nobject = "object";
  92
  93     private static Name Ndefun = "defun";
  94     private static Name Nfname = "fname";
  95     private static Name Nargs = "args";
  96     private static Name Noptional = "optional";
  97     private static Name Nrest = "rest";
  98     private static Name Nbody = "body";
  99
 100     private static Name Ndefvar = "defvar";
 101     private static Name Ndescription = "description";
 102     private static Name Nrange = "range";
 103
 104     private static Name Nprogn = "progn";
 105
 106     internal abstract class Function
 107     {
 108       public readonly Name name;
 109       public int min_arg, max_arg;
 110
 111       public Function (Name name, int min_arg, int max_arg)
 112       {
 113         this.name = name;
 114         this.min_arg = min_arg;
 115         this.max_arg = max_arg;
 116       }
 117
 118       public abstract object Call (Xex[] args, Domain domain);
 119
 120       public override string ToString ()
 121       {
 122         return name;
 123       }
 124
 125       internal class Subroutine : Function
 126       {
 127         public Builtin builtin;
 128
 129         public Subroutine (Builtin builtin, Name name,
 130                            int min_arg, int max_arg)
 131           : base (name, min_arg, max_arg)
 132           {
 133             this.builtin = builtin;
 134           }
 135
 136         public override object Call (Xex[] args, Domain domain)
 137         {
 138           object result;
 139
 140           foreach (Xex a in args)
 141             if (a.Eval (domain) == null)
 142               throw new Exception (a + ":evaled to null");
 143           Console.Write ("calling (" + this);
 144           foreach (Xex a in args)
 145             Console.Write (" " + a);
 146           Console.Write (") => ");
 147           result = builtin (args, domain);
 148           Console.WriteLine (result);
 149           return result;
 150         }
 151       }
 152
 153       internal class SpecialForm : Function
 154       {
 155         public Builtin builtin;
 156
 157         public SpecialForm (Builtin builtin, Name name,
 158                             int min_arg, int max_arg)
 159           : base (name, min_arg, max_arg)
 160           {
 161             this.builtin = builtin;
 162           }
 163
 164         public override object Call (Xex[] args, Domain domain)
 165         {
 166           object result;
 167
 168           Console.Write ("calling (" + this);
 169           foreach (Xex a in args)
 170             Console.Write (" " + a);
 171           Console.Write (") => ");
 172           result = builtin (args, domain);
 173           Console.WriteLine (result);
 174           return result;
 175         }
 176       }
 177
 178       internal class Lambda : Function
 179       {
 180         internal bool args_evaled = true;
 181         internal Name[] args;
 182         internal Xex[] body;
 183
 184         public Lambda (XmlNode node)
 185         {
 186           Name name = node.Attributes[Nfname].Value;
 187           int nargs = 0, noptions = 0, nrest = 0;
 188           XmlNode n;
 189
 190           node = node.FirstChild;
 191           if (node != null && node.Name == Nargs)
 192             {
 193               for (XmlNode n = node.FirstChild; n != null; n = n.NextSibling)
 194                 {
 195                   if (n.Name == Noptional || n.Name == Nrest)
 196                     break;
 197                   nargs++;
 198                 }
 199               if (n != null && n.Name == Noptional)
 200                 for (n = n.NextSibling; n != null; n = n.NextSibling)
 201               {
 202                 if (n.Name == Nrest)
 203                   break;
 204                 noptions++;
 205               }
 206           if (n != null && n.Name == Nrest)
 207             for (n = n.NextSibling; n != null; n = n.NextSibling)
 208               nrest++;
 209           min_arg = nargs;
 210           max_arg = nargs + noptions + nrest;
 211           if (nrest == 1)
 212             max_arg = - max_arg;
 213
 214
 215           args = new Xex[nargs];
 216           node = node.FirstChild;
 217           for (int i = 0; i < nargs; node = node.NextSibling)
 218             if (node.Name != Noptional && node.Name != Nrest)
 219               args[i++] = New (node, domain);
 220         }
 221
 222         public void SetBody (XmlNode node, Domain domain)
 223         {
 224           XmlNodeList nlist = node.ChildNodes;
 225
 226           body = new Xex[nlist.Count];
 227           for (int i = 0; i < nlist.Count; i++)
 228             body[i] = New (nlist[i], domain);
 229         }
 230
 231         public void Setup (XmlNode node, Domain domain)
 232         {
 233           node = node.FirstChild;
 234           if (node.Name == Nargs)
 235             {
 236               SetArgs (node, max_arg, domain);
 237               node = node.NextSibling;
 238             }
 239           if (node.Name == Nbody)
 240             SetBody (node, domain);
 241         }
 242
 243         public override object Call (Xex[] args, Domain domain)
 244         {
 245           Bindings current = domain.bindings;
 246           object result = false;
 247
 248           try {
 249             int i;
 250             for (i = 0; i < min_arg; i++)
 251               {
 252                 Xex a = this.args[i];
 253                 bool isdirect = a is Xex.Const;
 254                 Name name = (isdirect
 255                              ? (Name) a.val : ((Xex.Varref) a).vari.name);
 256                 Variable var = domain.GetVar (name);
 257
 258                 if (isdirect)
 259                   domain.Bind (var, args[i]);
 260                 else
 261                   domain.Bind (var, args[i].Eval (domain));
 262               }
 263             Console.Write ("calling (" + this);
 264             foreach (Xex e in body)
 265               result = e.Eval (domain);
 266             Console.WriteLine (result);
 267           } finally {
 268             domain.UnboundTo (current);
 269           }
 270           return result;
 271         }
 272
 273         public override string ToString ()
 274         {
 275           string str = "(" + name;
 276           foreach (Xex a in args)
 277             str += " " + a;
 278           return (str + ")");
 279         }
 280       }
 281     }
 282
 283     internal abstract class Variable
 284     {
 285       public readonly Name name;
 286       public readonly Name type;
 287       internal object val;
 288
 289       public Variable (Name name, Name type, object value)
 290       {
 291         if (value != null)
 292           Value = value;
 293         this.name = name;
 294         this.type = type;
 295       }
 296
 297       public object Value
 298       {
 299         get { return val; }
 300         set
 301           {
 302             if (! ValueP (value))
 303               throw new Exception ("Invalid value type: " + value);
 304             val = value;
 305           }
 306       }
 307
 308       public abstract bool ValueP (object value);
 309
 310       public override string ToString () { return name + "=" + val; }
 311     }
 312
 313     internal class VarInt : Variable
 314     {
 315       public struct Range
 316       {
 317         public int from, to;
 318       }
 319
 320       public Range[] ranges;
 321
 322       public VarInt (Name name, object value) : base (name, Ninteger, value) { }
 323
 324       public override bool ValueP (object value)
 325       {
 326         int i;
 327
 328         if (! (value is int))
 329           return false;
 330         if (ranges == null)
 331           return true;
 332         i = (int) value;
 333         foreach (Range r in ranges)
 334           if (i >= r.from && i <= r.to)
 335             return true;
 336         return false;
 337       }
 338     }
 339
 340     internal class VarStr : Variable
 341     {
 342       public string[] ranges;
 343
 344       public VarStr (Name name, object value) : base (name, Nstring, value) { }
 345
 346       public override bool ValueP (object value)
 347       {
 348         string str;
 349
 350         if (! (value is string))
 351           return false;
 352         if (ranges == null)
 353           return true;
 354         str = (string) value;
 355         foreach (string s in ranges)
 356           if (s == str)
 357             return true;
 358         return false;
 359       }
 360     }
 361
 362     internal class VarBool : Variable
 363     {
 364       public VarBool (Name name, object value)
 365         : base (name, Nboolean, value) { }
 366
 367       public override bool ValueP (object value)
 368       {
 369         if (! (value is bool))
 370           return false;
 371         return true;
 372       }
 373     }
 374
 375     internal class VarMisc : Variable
 376     {
 377       public VarMisc (Name name, object value) : base (name, Nobject, value) { }
 378
 379       public override bool ValueP (object value)
 380       {
 381         return true;
 382       }
 383     }
 384
 385     internal class Bindings
 386     {
 387       private Variable vari;
 388       private object old_value;
 389       private Bindings next;
 390
 391       private Bindings (Variable vari, object value)
 392       {
 393         this.vari = vari;
 394         old_value = value;
 395       }
 396
 397       public static Bindings Bind (Bindings bindings,
 398                                    Variable vari, object value)
 399       {
 400         Bindings b = new Bindings (vari, vari.val);
 401
 402         b.vari.Value = value;
 403         b.next = bindings;
 404         return b;
 405       }
 406
 407       internal Bindings UnboundTo (Bindings boundary)
 408       {
 409         for (Bindings b = this; b != boundary; b = b.next)
 410           vari.val = b.old_value;
 411         return boundary;
 412       }
 413
 414       public override string ToString ()
 415       {
 416         string str = "(bindings";
 417         for (Bindings b = this; b != null; b = b.next)
 418           str += " " + vari;
 419         return str + ")";
 420       }
 421     }
 422
 423 #if false
 424     internal class ThrowException : Exception
 425     {
 426       Name tag;
 427       public object value;
 428
 429       public ThrowException (Name tag, object value) : base ()
 430         {
 431           this.tag = tag;
 432           this.value = value;
 433         }
 434     }
 435 #endif
 436
 437     public class Domain
 438     {
 439       public object context;
 440
 441       internal Dictionary<Name, Function> functions;
 442       internal Dictionary<Name, Variable> variables;
 443       internal Bindings bindings;
 444
 445       internal Domain ()
 446       {
 447         functions = new Dictionary<Name, Function> ();
 448         variables = new Dictionary<Name, Variable> ();
 449       }
 450
 451       public Domain (object context) : this (basic, context)
 452       {
 453       }
 454
 455       public Domain (Domain parent, object context)
 456       {
 457         functions = new Dictionary<Name, Function> (parent.functions);
 458         variables = new Dictionary<Name, Variable> (parent.variables);
 459         this.context = context;
 460       }
 461
 462       internal void Bind (Variable vari, object value)
 463       {
 464         bindings = Bindings.Bind (bindings, vari, value);
 465         Console.WriteLine ("binding " + vari);
 466       }
 467
 468       internal void UnboundTo (Bindings boundary)
 469       {
 470         if (bindings != null)
 471           bindings = bindings.UnboundTo (boundary);
 472       }
 473
 474       public void DefSubr (Builtin builtin, string str,
 475                            int min_arg, int max_arg)
 476       {
 477         Name name = str;
 478         functions[name]
 479           = new Function.Subroutine (builtin, name, min_arg, max_arg);
 480       }
 481
 482       public void DefSpecial (Builtin builtin, string str,
 483                               int min_arg, int max_arg)
 484       {
 485         Name name = str;
 486         functions[name]
 487           = new Function.SpecialForm (builtin, name, min_arg, max_arg);
 488       }
 489
 490       private static Name ParseHead (XmlNode node, out bool evaled,
 491                                      out int min_arg, out int max_arg)
 492       {
 493         Name name = node.Attributes[Nfname].Value;
 494         int nargs = 0, noptions = 0, nrest = 0;
 495         XmlNode n;
 496
 497         for (n = node.FirstChild; n != null; n = n.NextSibling)
 498           {
 499             if (n.Name == Noptional || n.Name == Nrest)
 500               break;
 501             nargs++;
 502           }
 503         if (n != null && n.Name == Noptional)
 504           for (n = n.NextSibling; n != null; n = n.NextSibling)
 505             {
 506               if (n.Name == Nrest)
 507                 break;
 508               noptions++;
 509             }
 510         if (n != null && n.Name == Nrest)
 511           for (n = n.NextSibling; n != null; n = n.NextSibling)
 512             nrest++;
 513         min_arg = nargs;
 514         max_arg = nargs + noptions + nrest;
 515         if (nrest == 1)
 516           max_arg = - max_arg;
 517         return name;
 518       }
 519
 520       internal Function.Lambda RegisterFunction (XmlNode node)
 521       {
 522         bool evaled;
 523         int min_arg, max_arg;
 524         Name name = ParseHead (node, out evaled, out min_arg, out max_arg);
 525         Function.Lambda lambda = new Function.Lambda (name, min_arg, max_arg);
 526
 527         functions[name] = lambda;
 528         return lambda;
 529       }
 530
 531       internal Function Defun (XmlNode node)
 532       {
 533         Name name = node.Attributes[Nfname].Value;
 534         Function func;
 535
 536         if (! functions.TryGetValue (name, out func))
 537           func = RegisterFunction (node);
 538         ((Function.Lambda) func).Setup (node, this);
 539         return func;
 540       }
 541
 542       public void Defvar (Name name, XmlNode node)
 543       {
 544         Variable vari;
 545
 546         if (node.Name == Ndescription)
 547           node = node.NextSibling;
 548         if (node != null)
 549           {
 550             Name type = node.Name;
 551             XmlNodeList range_list = null;
 552             int nranges = 0;
 553
 554             node = node.NextSibling;
 555             if (node != null)
 556               {
 557                 range_list = node.ChildNodes;
 558                 nranges = range_list.Count;
 559               }
 560
 561             if (type == Ninteger)
 562               {
 563                 VarInt vi = new VarInt (name, parse_integer (val));
 564                 if (range_list != null)
 565                   {
 566                     vi.ranges = new VarInt.Range[nranges];
 567
 568                     for (int i = 0; i < nranges; i++)
 569                       {
 570                         XmlNode n = range_list[i];
 571
 572                         if (n.Name == Nrange)
 573                           {
 574                             vi.ranges[i].from =
 575                               parse_integer (n.FirstChild.Value);
 576                             vi.ranges[i].to =
 577                               parse_integer (n.LastChild.Value);
 578                           }
 579                         else
 580                           {
 581                             int num = parse_integer (n.Value);
 582                             vi.ranges[i].from = vi.ranges[i].to = num;
 583                           }
 584                       }
 585                   }
 586                 vari = vi;
 587               }
 588             else if (type == Nstring)
 589               {
 590                 VarStr vs = new VarStr (name, val);
 591                 if (range_list != null)
 592                   vs.ranges = new string[nranges];
 593                 for (int i = 0; i < nranges; i++)
 594                   vs.ranges[i] = range_list[i].Value;
 595                 vari = vs;
 596               }
 597             else if (type == Nboolean)
 598               {
 599                 vari = new VarBool (name, val == "true");
 600               }
 601             else
 602               throw new Exception ("Unknown type: " + type);
 603           }
 604         else
 605           vari = new VarMisc (name, null);
 606         variables[name] = vari;
 607       }
 608
 609       internal Function GetFunc (Name name)
 610       {
 611         Function func;
 612
 613         if (! functions.TryGetValue (name, out func))
 614           throw new Exception ("Unknown function: " + name);
 615         return func;
 616       }
 617
 618       public bool CopyFunc (Domain domain, Name name)
 619       {
 620         Function func = GetFunc (name);
 621
 622         domain.functions[name] = func;
 623         return true;
 624       }
 625
 626       public void CopyFunc (Domain domain)
 627       {
 628         foreach (KeyValuePair<Name, Function> kv in functions)
 629           domain.functions[kv.Key] = kv.Value;
 630       }
 631
 632       internal Variable GetVar (Name name)
 633       {
 634         Variable vari;
 635
 636         if (! variables.TryGetValue (name, out vari))
 637           variables[name] = vari = new VarMisc (name, null);
 638         return vari;
 639       }
 640
 641       internal Variable GetVar (Xex e)
 642       {
 643         if (! (e.val is Name))
 644           throw new Exception ("Not a symbol" + e.val);
 645         return GetVar ((Name) e.val);
 646       }
 647
 648       public override string ToString ()
 649       {
 650         string str = "<(functions";
 651         foreach (KeyValuePair<Name, Function> kv in functions)
 652           str += " " + kv.Key;
 653         str += ") (variabls";
 654         foreach (KeyValuePair<Name, Variable> kv in variables)
 655           str += " " + kv.Key;
 656         str += ")";
 657         if (bindings != null)
 658           str += " " + bindings;
 659         if (context != null)
 660           str += " (" + context + ")";
 661         str += ">";
 662         return str;
 663       }
 664     }
 665
 666     public delegate object Builtin (Xex[] args, Domain domain);
 667
 668     private static Domain basic = new Domain ();
 669
 670     internal static Function Fprogn;
 671
 672     static Xex ()
 673     {
 674       basic.DefSubr (set_value, "set", 2, 2);
 675       basic.DefSubr (set_value, "=", 2, 2);
 676       basic.DefSubr (and, "and", 1, -1);
 677       basic.DefSubr (and, "&&", 1, -1);
 678       basic.DefSubr (or, "or", 1, -1);
 679       basic.DefSubr (or, "||", 1, -1);
 680       basic.DefSubr (not, "not", 1, 1);
 681       basic.DefSubr (not, "!", 1, 1);
 682       basic.DefSubr (add, "add", 2, -1);
 683       basic.DefSubr (add, "+", 2, -1);
 684       basic.DefSubr (mul, "mul", 2, -1);
 685       basic.DefSubr (mul, "*", 2, -1);
 686       basic.DefSubr (sub, "sub", 1, -1);
 687       basic.DefSubr (sub, "-", 1, -1);
 688       basic.DefSubr (div, "div", 2, -1);
 689       basic.DefSubr (div, "/", 2, -1);
 690       basic.DefSubr (mod, "mod", 2, 2);
 691       basic.DefSubr (mod, "%", 2, 2);
 692       basic.DefSubr (logior, "logior", 2, -1);
 693       basic.DefSubr (logior, "|", 2, -1);
 694       basic.DefSubr (logand, "logand", 2, -1);
 695       basic.DefSubr (logand, "&", 2, -1);
 696       basic.DefSubr (add_set, "add-set", 2, -1);
 697       basic.DefSubr (add_set, "+=", 2, -1);
 698       basic.DefSubr (mul_set, "mul-set", 2, -1);
 699       basic.DefSubr (mul_set, "*=", 2, -1);
 700       basic.DefSubr (sub_set, "sub-set", 2, -1);
 701       basic.DefSubr (sub_set, "-=", 2, -1);
 702       basic.DefSubr (div_set, "div-set", 2, -1);
 703       basic.DefSubr (div_set, "/=", 2, -1);
 704       basic.DefSubr (mod_set, "mod-set", 2, 2);
 705       basic.DefSubr (mod_set, "%=", 2, 2);
 706       basic.DefSubr (logior_set, "logior-set", 2, -1);
 707       basic.DefSubr (logior_set, "|=", 2, -1);
 708       basic.DefSubr (logand_set, "logand-set", 2, -1);
 709       basic.DefSubr (logand_set, "&=", 2, -1);
 710       basic.DefSubr (lsh, "lsh", 2, 2);
 711       basic.DefSubr (lsh, "<<", 2, 2);
 712       basic.DefSubr (rsh, "rsh", 2, 2);
 713       basic.DefSubr (rsh, ">>", 2, 2);
 714       basic.DefSubr (lsh_set, "lsh-set", 2, 2);
 715       basic.DefSubr (lsh_set, "<<=", 2, 2);
 716       basic.DefSubr (rsh_set, "rsh-set", 2, 2);
 717       basic.DefSubr (rsh_set, ">>=", 2, 2);
 718       basic.DefSubr (eq, "eq", 2, -1);
 719       basic.DefSubr (eq, "==", 2, -1);
 720       basic.DefSubr (noteq, "noteq", 2, 2);
 721       basic.DefSubr (noteq, "!=", 2, 2);
 722       basic.DefSubr (less_than, "lt", 2, -1);
 723       basic.DefSubr (less_than, "<", 2, -1);
 724       basic.DefSubr (less_eq, "le", 2, -1);
 725       basic.DefSubr (less_eq, "<=", 2, -1);
 726       basic.DefSubr (greater_than, "gt", 2, -1);
 727       basic.DefSubr (greater_than, ">", 2, -1);
 728       basic.DefSubr (greater_eq, "ge", 2, -1);
 729       basic.DefSubr (greater_eq, ">=", 2, -1);
 730       basic.DefSubr (eval_clause, "eval", 1, 1);
 731       basic.DefSpecial (progn_clause, "progn", 0, -1);
 732       basic.DefSpecial (progn_clause, "expr", 0, -1);
 733       basic.DefSpecial (if_clause, "if", 2, -1);
 734       basic.DefSpecial (when_clause, "when", 1, -1);
 735       basic.DefSpecial (while_clause, "while", 1, -1);
 736
 737       Fprogn = basic.GetFunc (Nprogn);
 738     }
 739
 740     private static bool is_true (object val)
 741     {
 742       return (val is bool ? (bool) val
 743               : val is int ? (int) val == 0
 744               : true);
 745     }
 746
 747     private static object set_value (Xex[] args, Domain domain)
 748     {
 749       Variable vari = domain.GetVar (args[0]);
 750
 751       vari.Value = args[1].val;
 752       return vari.val;
 753     }
 754
 755     private static object and (Xex[] args, Domain domain)
 756     {
 757       foreach (Xex arg in args)
 758         if (! is_true (arg.val))
 759           return false;
 760       return true;
 761     }
 762
 763     private static object or (Xex[] args, Domain domain)
 764     {
 765       foreach (Xex arg in args)
 766         if (is_true (arg.val))
 767           return true;
 768       return false;
 769     }
 770
 771     private static object not (Xex[] args, Domain domain)
 772     {
 773       return ! is_true (args[0].val);
 774     }
 775
 776     private static object add (Xex[] args, Domain domain)
 777     {
 778       int n = 0;
 779       foreach (Xex e in args)
 780         n += (int) e.val;
 781       return n;
 782     }
 783
 784     private static object mul (Xex[] args, Domain domain)
 785     {
 786       int n = 1;
 787       foreach (Xex e in args)
 788         n *= (int) e.val;
 789       return n;
 790     }
 791
 792     private static object sub (Xex[] args, Domain domain)
 793     {
 794       int n = (int) args[0].val;
 795       if (args.Length == 1)
 796         return - n;
 797       for (int i = 1; i < args.Length; i++)
 798         n -= (int) args[i].val;
 799       return n;
 800     }
 801
 802     private static object div (Xex[] args, Domain domain)
 803     {
 804       int n = (int) args[0].val;
 805       for (int i = 1; i < args.Length; i++)
 806         n /= (int) args[i].val;
 807       return n;
 808     }
 809
 810     private static object mod (Xex[] args, Domain domain)
 811     {
 812       return ((int) args[0].val % (int) args[1].val);
 813     }
 814
 815     private static object logior (Xex[] args, Domain domain)
 816     {
 817       int n = 0;
 818       foreach (Xex e in args)
 819         n |= (int) e.val;
 820       return n;
 821     }
 822
 823     private static object logand (Xex[] args, Domain domain)
 824     {
 825       int n = (int) args[0].val;
 826       for (int i = 1; i < args.Length; i++)
 827         n &= (int) args[i].val;
 828       return n;
 829     }
 830
 831     private static object add_set (Xex[] args, Domain domain)
 832     {
 833       Variable vari = domain.GetVar (args[0]);
 834       int n = (int) vari.val;
 835
 836       for (int i = 1; i < args.Length; i++)
 837         n += (int) args[i].val;
 838       vari.val = n;
 839       return n;
 840     }
 841
 842     private static object mul_set (Xex[] args, Domain domain)
 843     {
 844       Variable vari = domain.GetVar (args[0]);
 845       int n = (int) vari.val;
 846
 847       for (int i = 1; i < args.Length; i++)
 848         n *= (int) args[i].val;
 849       vari.val = n;
 850       return n;
 851     }
 852
 853     private static object sub_set (Xex[] args, Domain domain)
 854     {
 855       Variable vari = domain.GetVar (args[0]);
 856       int n = (int) vari.val;
 857
 858       for (int i = 1; i < args.Length; i++)
 859         n -= (int) args[i].val;
 860       vari.val = n;
 861       return n;
 862     }
 863
 864     private static object div_set (Xex[] args, Domain domain)
 865     {
 866       Variable vari = domain.GetVar (args[0]);
 867       int n = (int) vari.val;
 868
 869       for (int i = 1; i < args.Length; i++)
 870         n /= (int) args[i].val;
 871       vari.val = n;
 872       return n;
 873     }
 874
 875     private static object mod_set (Xex[] args, Domain domain)
 876     {
 877       Variable vari = domain.GetVar (args[0]);
 878       int n = (int) vari.val;
 879
 880       for (int i = 1; i < args.Length; i++)
 881         n %= (int) args[i].val;
 882       vari.val = n;
 883       return n;
 884     }
 885
 886     private static object logior_set (Xex[] args, Domain domain)
 887     {
 888       Variable vari = domain.GetVar (args[0]);
 889       int n = (int) vari.val;
 890
 891       for (int i = 1; i < args.Length; i++)
 892         n |= (int) args[i].val;
 893       vari.val = n;
 894       return n;
 895     }
 896
 897     private static object logand_set (Xex[] args, Domain domain)
 898     {
 899       Variable vari = domain.GetVar (args[0]);
 900       int n = (int) vari.val;
 901
 902       for (int i = 1; i < args.Length; i++)
 903         n &= (int) args[i].val;
 904       vari.val = n;
 905       return n;
 906     }
 907
 908     private static object lsh (Xex[] args, Domain domain)
 909     {
 910       return (int) args[0].val << (int) args[1].val;
 911     }
 912
 913     private static object lsh_set (Xex[] args, Domain domain)
 914     {
 915       Variable vari = domain.GetVar (args[0]);
 916       int n = (int) vari.val;
 917
 918       n <<= (int) args[1].val;
 919       vari.val = n;
 920       return n;
 921     }
 922
 923     private static object rsh (Xex[] args, Domain domain)
 924     {
 925       return (int) args[0].val >> (int) args[1].val;
 926     }
 927
 928     private static object rsh_set (Xex[] args, Domain domain)
 929     {
 930       Variable vari = domain.GetVar (args[0]);
 931       int n = (int) vari.val;
 932
 933       n >>= (int) args[1].val;
 934       vari.val = n;
 935       return n;
 936     }
 937
 938     private static object eq (Xex[] args, Domain domain)
 939     {
 940       int n = (int) args[0].val;
 941
 942       for (int i = 1; i < args.Length; i++)
 943         if (n != (int) args[i].val)
 944           return false;
 945       return true;
 946     }
 947
 948     private static object noteq (Xex[] args, Domain domain)
 949     {
 950       return ((int) args[0].val != (int) args[1].val);
 951     }
 952
 953     private static object less_than (Xex[] args, Domain domain)
 954     {
 955       int n = (int) args[0].val;
 956
 957       for (int i = 1; i < args.Length; i++)
 958         {
 959           int n1 = (int) args[i].val;
 960           if (n >= n1)
 961             return false;
 962           n = n1;
 963         }
 964       return true;
 965     }
 966
 967     private static object less_eq (Xex[] args, Domain domain)
 968     {
 969       int n = (int) args[0].val;
 970       for (int i = 1; i < args.Length; i++)
 971         {
 972           int n1 = (int) args[i].val;
 973           if (n > n1)
 974             return false;
 975           n = n1;
 976         }
 977       return true;
 978     }
 979
 980     private static object greater_than (Xex[] args, Domain domain)
 981     {
 982       int n = (int) args[0].val;
 983       for (int i = 1; i < args.Length; i++)
 984         {
 985           int n1 = (int) args[i].val;
 986           if (n <= n1)
 987             return false;
 988           n = n1;
 989         }
 990       return true;
 991     }
 992
 993     private static object greater_eq (Xex[] args, Domain domain)
 994     {
 995       int n = (int) args[0].val;
 996       for (int i = 1; i < args.Length; i++)
 997         {
 998           int n1 = (int) args[i].val;
 999           if (n < n1)
1000             return false;
1001           n = n1;
1002         }
1003       return true;
1004     }
1005
1006     private static object eval_clause (Xex[] args, Domain domain)
1007     {
1008       return ((Xex) args[0].val).Eval (domain);
1009     }
1010
1011     private static object progn_clause (Xex[] args, Domain domain)
1012     {
1013       object result = true;
1014
1015       foreach (Xex e in args)
1016         result = e.Eval (domain);
1017       return result;
1018     }
1019
1020     private static object if_clause (Xex[] args, Domain domain)
1021     {
1022       object result;
1023
1024       if (is_true (args[0].Eval (domain)))
1025         result = args[1].Eval (domain);
1026       else
1027         {
1028           result = false;
1029           for (int i = 2; i < args.Length; i++)
1030             result = args[i].Eval (domain);
1031         }
1032       return result;
1033     }
1034
1035     private static object when_clause (Xex[] args, Domain domain)
1036     {
1037       if (! is_true (args[0].Eval (domain)))
1038         return false;
1039
1040       object result = true;
1041       for (int i = 1; i < args.Length; i++)
1042         result = args[i].Eval (domain);
1043       return result;
1044     }
1045
1046     private static object while_clause (Xex[] args, Domain domain)
1047     {
1048       while (is_true (args[0].Eval (domain)))
1049         for (int i = 1; i < args.Length; i++)
1050           args[i].Eval (domain);
1051       return false;
1052     }
1053
1054     // FUNCALL: function != null
1055     // VARREF:  function == null, args[0] = DIRECT-SYMBOL
1056     // DIRECT:  function == null, args == null
1057
1058     private object val;
1059     public abstract object Eval (Domain domain);
1060     public object Val { get { return val; } }
1061
1062     private class Funcall : Xex
1063     {
1064       internal Function func;
1065       internal Xex[] args;
1066
1067       public Funcall (Function func, Xex[] args)
1068         {
1069           this.func = func;
1070           this.args = args;
1071         }
1072
1073       public override object Eval (Domain domain)
1074       {
1075         val = func.Call (args, domain);
1076         return val;
1077       }
1078
1079       public override string ToString ()
1080       {
1081         string str = "(" + func.name;
1082         if (args != null)
1083           foreach (Xex e in args)
1084             str += " " + e.ToString ();
1085         return (str + ")");
1086       }
1087     }
1088
1089     private class Varref : Xex
1090     {
1091       internal Variable vari;
1092
1093       public Varref (Variable vari)
1094         {
1095           this.vari = vari;
1096         }
1097
1098       public override object Eval (Domain domain)
1099       {
1100         val = vari.val;
1101         return val;
1102       }
1103
1104       public override string ToString ()
1105       {
1106         return "$" + vari.name + "/" + vari.val;
1107       }
1108     }
1109
1110     private class Const : Xex
1111     {
1112       public Const (object val)
1113         {
1114           this.val = val;
1115         }
1116
1117       public override object Eval (Domain domain)
1118       {
1119         return val;
1120       }
1121
1122       public override string ToString ()
1123       {
1124         return val.ToString ();
1125       }
1126     }
1127
1128     internal static int parse_integer (string str)
1129     {
1130       int len = str.Length;
1131       bool negative = false;
1132
1133       if (len <= 1)
1134         return (len == 0 ? 0 : str[0] - '0');
1135
1136       int c = str[0];
1137       int i;
1138
1139       if (c == '0' && str[1] == 'x')
1140         {
1141           i = 0;
1142           for (int idx = 2; idx < len; idx++)
1143             {
1144               c = str[idx];
1145               if (c < '0')
1146                 break;
1147               else if (c <= '9')
1148                 i = i * 16 + (c - '0');
1149               else if (c < 'A')
1150                 break;
1151               else if (c <= 'F')
1152                 i = i * 16 + (c - 'A');
1153               else if (c < 'a')
1154                 break;
1155               else if (c <= 'f')
1156                 i = i * 16 + (c - 'a');
1157               else
1158                 break;
1159             }
1160           return i;
1161         }
1162       if (c == '-')
1163         negative = true;
1164       i = c - '0';
1165       for (int idx = 1; idx < len; idx++)
1166         {
1167           c = str[idx];
1168           if (c < '0' || c > '9')
1169             break;
1170           i = i * 10 + (c - '0');
1171         }
1172       return negative ? - i : i;
1173     }
1174
1175     private static int pre_parse (XmlNodeList nlist, Domain domain)
1176     {
1177       int len = 0;
1178       foreach (XmlNode node in nlist)
1179         {
1180           if (node.Name == Ndefun)
1181             domain.RegisterFunction (node);
1182           else if (node.Name == Ndefvar)
1183             domain.Defvar ((Name) node.Attributes[0].Value, node.FirstChild);
1184           else
1185             len++;
1186         }
1187       return len;
1188     }
1189
1190     private static void post_parse (XmlNodeList nlist, Xex[] args,
1191                                     Domain domain)
1192     {
1193       for (int i = 0, j = 0; i < nlist.Count; i++)
1194         {
1195           XmlNode node = nlist[i];
1196
1197           if (node.Name == Ndefun)
1198             domain.Defun (node);
1199           else if (node.Name != Ndefvar)
1200             args[j++] = New (node, domain);
1201         }
1202     }
1203
1204     public static Xex New (string url, Domain domain)
1205     {
1206       XmlDocument doc = new XmlDocument (Name.Table);
1207       XmlNode node;
1208
1209       using (XmlTextReader reader = new XmlTextReader (url, Name.Table))
1210         {
1211           do {
1212             reader.Read ();
1213           } while (reader.NodeType != XmlNodeType.None
1214                    && (reader.NodeType != XmlNodeType.Element
1215                        || Nexpr != reader.Name));
1216           if (reader.NodeType == XmlNodeType.None)
1217             throw new Exception ("Node <expr> not found");
1218           node = doc.ReadNode (reader);
1219         }
1220
1221       return New (node, domain);
1222     }
1223
1224     // EXPR = SYMBOL | MTEXT | INTEGER | FUNCALL | PROGN
1225     // FUNCALL = '(' SYMBOL EXPR* ')'
1226     // PROGN = '(' EXPR * ')'
1227     public static Xex New (XmlNode node, Domain domain)
1228     {
1229       Name name = node.Name;
1230       Xex xex;
1231       if (name == Nvariable)
1232         {
1233           Variable vari = domain.GetVar ((Name) node.Attributes[0].Value);
1234           xex = new Xex.Varref (vari);
1235         }
1236       else if (name == Ninteger)
1237         xex = new Xex.Const (parse_integer (node.InnerText));
1238       else if (name == Nstring)
1239         xex = new Xex.Const (node.InnerText);
1240       else if (name == Nsymbol)
1241         xex = new Xex.Const ((Name) node.InnerText);
1242       else if (name == Nboolean)
1243         xex = new Xex.Const (node.InnerText == "true");
1244       else if (name == Nlist)
1245         {
1246           List<Xex> list = new List<Xex> ();
1247           for (XmlNode n = node.FirstChild; n != null; n = n.NextSibling)
1248             list.Add (New (n, domain));
1249           xex = new Xex.Const (list);
1250         }
1251       else
1252         {
1253           if (name == Nfuncall)
1254             name = node.Attributes[0].Value;
1255           Function func = domain.GetFunc (name);
1256
1257           XmlNodeList nlist = node.ChildNodes;
1258           int nargs = nlist.Count;
1259
1260           if (nargs < func.min_arg
1261               || (func.max_arg >= 0 && nargs > func.max_arg))
1262             throw new Exception ("Invalid number of arguments to: "
1263                                  + name + " " + nargs);
1264           nargs =  pre_parse (nlist, domain);
1265           Xex[] args = new Xex[nargs];
1266           post_parse (nlist, args, domain);
1267           xex = new Xex.Funcall (func, args);
1268         }
1269       return xex;
1270     }
1271   }
1272 }