mcs/class/System/System.Text.RegularExpressions/arch.cs

   1 //
   2 // assembly:    System
   3 // namespace:   System.Text.RegularExpressions
   4 // file:        arch.cs
   5 //
   6 // author:      Dan Lewis (dlewis@gmx.co.uk)
   7 //              (c) 2002
   8
   9 //
  10 // Permission is hereby granted, free of charge, to any person obtaining
  11 // a copy of this software and associated documentation files (the
  12 // "Software"), to deal in the Software without restriction, including
  13 // without limitation the rights to use, copy, modify, merge, publish,
  14 // distribute, sublicense, and/or sell copies of the Software, and to
  15 // permit persons to whom the Software is furnished to do so, subject to
  16 // the following conditions:
  17 //
  18 // The above copyright notice and this permission notice shall be
  19 // included in all copies or substantial portions of the Software.
  20 //
  21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  22 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  23 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  24 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  25 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  26 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  27 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  28 //
  29
  30 using System;
  31 using System.Collections;
  32
  33 namespace System.Text.RegularExpressions {
  34
  35         enum OpCode : ushort {
  36                 False           = 0,    // always fails
  37                 True,                   // always succeeds
  38
  39                 // matching
  40
  41                 Position,               // zero-width position assertion
  42                 String,                 // match string literal
  43                 Reference,              // back reference
  44
  45                 // character matching
  46
  47                 Character,              // match character exactly
  48                 Category,               // match character from category
  49                 Range,                  // match character from range
  50                 Set,                    // match character from set
  51                 In,                     // match character from group of tests
  52
  53                 // capturing
  54
  55                 Open,                   // open group
  56                 Close,                  // close group
  57                 Balance,                // balance groups
  58                 BalanceStart,           //track balance group length
  59
  60                 // control flow
  61
  62                 IfDefined,              // conditional on capture
  63                 Sub,                    // non-backtracking subexpression
  64                 Test,                   // non-backtracking lookahead/behind
  65                 Branch,                 // alternative expression
  66                 Jump,                   // unconditional goto
  67                 Repeat,                 // new repeat context
  68                 Until,                  // repeat subexpression within context
  69                 FastRepeat,             // repeat simple subexpression
  70                 Anchor,                 // anchoring expression
  71
  72                 // miscellaneous
  73
  74                 Info                    // pattern information
  75         }
  76
  77         [Flags]
  78         enum OpFlags : ushort {
  79                 None            = 0x000,
  80                 Negate          = 0x100,        // succeed on mismatch
  81                 IgnoreCase      = 0x200,        // case insensitive matching
  82                 RightToLeft     = 0x400,        // right-to-left matching
  83                 Lazy            = 0x800         // minimizing repeat
  84         }
  85
  86         enum Position : ushort {
  87                 Any,                    // anywhere
  88                 Start,                  // start of string                      \A
  89                 StartOfString,          // start of string                      \A
  90                 StartOfLine,            // start of line                        ^
  91                 StartOfScan,            // start of scan                        \G
  92                 End,                    // end or before newline at end         \Z
  93                 EndOfString,            // end of string                        \z
  94                 EndOfLine,              // end of line                          $
  95                 Boundary,               // word boundary                        \b
  96                 NonBoundary             // not word boundary                    \B
  97         };
  98
  99         // see category.cs for Category enum
 100
 101         interface IMachine {
 102                 Match Scan (Regex regex, string text, int start, int end);
 103         }
 104
 105         interface IMachineFactory {
 106                 IMachine NewInstance ();
 107                 IDictionary Mapping { get; set; }
 108                 int GroupCount { get; }
 109         }
 110
 111         // Anchor SKIP OFFSET
 112         //
 113         // Flags:       [RightToLeft] ??
 114         // SKIP:        relative address of tail expression
 115         // OFFSET:      offset of anchor from start of pattern
 116         //
 117         // Usage:
 118         //
 119         //      Anchor :1 OFFSET
 120         //              <expr>
 121         //              True
 122         // 1:   <tail>
 123         //
 124         // Notes:
 125         //
 126         // In practice, the anchoring expression is only going to be
 127         // Position (StartOfString, StartOfLine, StartOfScan) or String.
 128         // This is because the optimizer looks for position anchors at the
 129         // start of the expression, and if that fails it looks for the
 130         // longest substring. If an expression has neither a position
 131         // anchor or a longest substring anchor, then the anchoring expression
 132         // is left empty. Since an empty expression will anchor at any
 133         // position in any string, the entire input string will be scanned.
 134
 135         // String LEN STR...
 136         //
 137         // Flags:       [RightToLeft, IgnoreCase]
 138         // LEN:         length of string
 139         // STR:         string characters
 140
 141         // Branch SKIP
 142         //
 143         // SKIP:        relative address of next branch
 144         //
 145         //      Branch :1
 146         //              <alt expr 1>
 147         //              Jump :4
 148         // 1:   Branch :2
 149         //              <alt expr 2>
 150         //              Jump :4
 151         // 2:   Branch :3
 152         //              <alt expr 3>
 153         //              Jump :4
 154         // 3:   False
 155         // 4:   <tail>
 156
 157         // Repeat SKIP MIN MAX
 158         //
 159         // Flags:       [Lazy]
 160         // SKIP:        relative address of Until instruction
 161         // MIN:         minimum iterations
 162         // MAX:         maximum iterations (0xffff is infinity)
 163         //
 164         //      Repeat :1 MIN MAX
 165         //              <expr>
 166         //              Until
 167         // 1:   <tail>
 168
 169         // FastRepeat SKIP MIN MAX
 170         //
 171         // Flags:       [Lazy]
 172         // SKIP:        relative address of tail expression
 173         // MIN:         minimum iterations
 174         // MAX:         maximum iterations (0xffff is infinity)
 175         //
 176         //      FastRepeat :1 MIN MAX
 177         //              <expr>
 178         //              True
 179         // 1:   <tail>
 180         //
 181         // Notes:
 182         //
 183         // The subexpression of a FastRepeat construct must not contain any
 184         // complex operators. These include: Open, Close, Balance, Repeat,
 185         // FastRepeat, Sub, Test. In addition, the subexpression must have
 186         // been determined to have a fixed width.
 187
 188         // Sub SKIP
 189         //
 190         // SKIP:        relative address of tail expression
 191         //
 192         //      Sub :1
 193         //              <expr>
 194         // 1:   <tail>
 195         //
 196         // Notes:
 197         //
 198         // The Sub operator invokes an independent subexpression. This means
 199         // that the subexpression will match only once and so will not
 200         // participate in any backtracking.
 201
 202         // Test TSKIP FSKIP
 203         //
 204         // TSKIP:       relative address of true expression
 205         // FSKIP:       relative address of false expression
 206         //
 207         // Usage:       (?(?=test)true|false)
 208         //
 209         //      Test :1 :2
 210         //              <test expr>
 211         // 1:           <true expr>
 212         //              Jump
 213         // 2:           <false epxr>
 214         //      <tail>
 215         //
 216         // Usage:       (?(?=test)true)
 217         //
 218         //      Test :1 :2
 219         //              <test expr>
 220         // 1:           <true expr>
 221         // 2:   <tail>
 222         //
 223         // Usage:       (?=test)
 224         //
 225         //      Test :1 :2
 226         //              <test expr>
 227         // 1:           <true expr>
 228         //              Jump 3:
 229         // 2:           False
 230         // 3:           <tail>
 231         //
 232         // Notes:
 233         //
 234         // For negative lookaheads, just swap the values of TSKIP and
 235         // FSKIP. For lookbehinds, the test expression must be compiled
 236         // in reverse. The test expression is always executed as an
 237         // independent subexpression, so its behaviour is non-backtracking
 238         // (like a Sub clause.)
 239
 240         // IfDefined SKIP GID
 241         //
 242         // SKIP:        relative address of else expression
 243         // GID:         number of group to check
 244         //
 245         // Usage:       (?(gid)true)
 246         //
 247         //      IfDefined :1
 248         //              <true expr>
 249         // 1:   <tail>
 250         //
 251         // Usage:       (?(gid)true|false)
 252         //
 253         //      IfDefined :1
 254         //              <true expr>
 255         //              Jump :2
 256         // 1:           <false expr>
 257         // 2:   <tail>
 258
 259         // Jump SKIP
 260         //
 261         // SKIP:        relative address of target expression
 262         //
 263         //      Jump :1
 264         //      ...
 265         // :1   <target expr>
 266
 267         // Character CHAR
 268         //
 269         // Flags:       [Negate, IgnoreCase, RightToLeft]
 270         // CHAR:        exact character to match
 271
 272         // Category CAT
 273         //
 274         // Flags:       [Negate, RightToLeft]
 275         // CAT:         category to match (see Category enum)
 276
 277         // Range LO HI
 278         //
 279         // Flags:       [Negate, IgnoreCase, RightToLeft]
 280         // LO:          lowest character in range
 281         // HI:          higest character in range
 282
 283         // Set LO LEN SET...
 284         //
 285         // Flags:       [Negate, IgnoreCase, RightToLeft]
 286         // LO:          lowest character in set
 287         // LEN:         number of words in set
 288         // SET:         bit array representing characters in set
 289         //
 290         // Notes:
 291         //
 292         // Each word in the set represents 16 characters, so the first word
 293         // defines membership for characters LO to LO + 15, the second for
 294         // LO + 16 to LO + 31, and so on up to LO + (LEN * 16 - 1). It is
 295         // up to the compiler to provide a compact representation for sparse
 296         // unicode sets. The simple way is to use Set 0 4096. Other methods
 297         // involve paritioning the set and placing the components into an
 298         // In block.
 299
 300         // In SKIP
 301         //
 302         // SKIP:        relative address of tail expression
 303         //
 304         // Usage:       [expr]
 305         //
 306         //      In :1
 307         //              <expr>
 308         //              True
 309         // :1   <tail>
 310         //
 311         // Usage:       [^expr]
 312         //
 313         //      In :1
 314         //              <expr>
 315         //              False
 316         // :1   <tail>
 317         //
 318         // Notes:
 319         //
 320         // The In instruction consumes a single character, using the flags
 321         // of the first instruction in the subexpression to determine its
 322         // IgnoreCase and RightToLeft properties. The subexpression is then
 323         // applied to the single character as a disjunction. If any instruction
 324         // in the subexpression succeeds, the entire In construct succeeds
 325         // and matching continues with the tail.
 326
 327         // Position POS
 328         //
 329         // POS:         position to match (see Position enum)
 330
 331         // Open GID
 332         //
 333         // GID:         number of group to open
 334
 335         // Close GID
 336         //
 337         // GID:         number of group to close
 338
 339         // Balance GID BAL
 340         //
 341         // GID:         number of capturing group (0 if none)
 342         // BAL:         number of group to undefine
 343
 344         // Info GROUPS MIN MAX
 345         //
 346         // GROUPS:      number of capturing groups
 347         // MIN:         minimum width of pattern
 348         // MAX:         maximum width of pattern (0xffff means undefined)
 349
 350         // False
 351
 352         // True
 353
 354         // Reference GID
 355         //
 356         // Flags:       [IgnoreCase, RightToLeft]
 357         // GID:         number of group to reference
 358 }