1 package kawa.lang; 2 import gnu.mapping.*; 3 import gnu.expr.*; 4 import java.io.*; 5 import gnu.lists.*; 6 import java.util.Vector ; 7 import gnu.text.*; 8 9 10 11 public class SyntaxPattern extends Pattern implements Externalizable 12 { 13 19 String program; 20 21 22 static final int MATCH_MISC = 0; 23 24 25 static final int MATCH_NIL = (1<<3)+MATCH_MISC; 26 27 30 static final int MATCH_VECTOR = (2<<3)+MATCH_MISC; 31 32 33 static final int MATCH_IGNORE = (3<<3)+MATCH_MISC; 34 35 38 static final int MATCH_WIDE = 1; 39 40 41 static final int MATCH_EQUALS = 2; 42 43 45 static final int MATCH_ANY = 3; 46 47 50 static final int MATCH_PAIR = 4; 51 52 61 static final int MATCH_LREPEAT = 5; 62 63 66 static final int MATCH_LENGTH = 6; 67 68 70 static final int MATCH_ANY_CAR = 7; 71 72 Object [] literals; 73 int varCount; 74 75 public int varCount() { return varCount; } 76 77 public boolean match (Object obj, Object [] vars, int start_vars) 78 { 79 boolean r = match(obj, vars, start_vars, 0, null); 80 if (false) { 82 OutPort err = OutPort.errDefault(); 83 err.print("{match "); 84 kawa.standard.Scheme.writeFormat.writeObject(obj, err); 85 err.print(" in "); 86 err.print(((Translator) Compilation.getCurrent()).getCurrentSyntax()); 87 if (r) 88 { 89 err.print(" -> vars: "); 90 for (int i = start_vars; i < vars.length; i++) 91 { 92 err.println(); 93 err.print(" " + i +" : "); 94 kawa.standard.Scheme.writeFormat.writeObject(vars[i], err); 95 } 96 err.println('}'); 97 } 98 else 99 err.println(" -> failed}"); 100 } 101 return r; 102 } 103 104 public SyntaxPattern (String program, Object [] literals, int varCount) 105 { 106 this.program = program; 107 this.literals = literals; 108 this.varCount = varCount; 109 } 110 111 public SyntaxPattern (Object pattern, 112 Object [] literal_identifiers, Translator tr) 113 { 114 this(new StringBuffer (), pattern, 115 null, literal_identifiers, tr); 116 } 117 118 SyntaxPattern (StringBuffer programbuf, Object pattern, 119 SyntaxForm syntax, Object [] literal_identifiers, 120 Translator tr) 121 { 122 Vector literalsbuf = new Vector (); 123 translate(pattern, programbuf, 124 literal_identifiers, 0, literalsbuf, null, '\0', tr); 125 program = programbuf.toString(); 126 literals = new Object [literalsbuf.size()]; 127 literalsbuf.copyInto(literals); 128 varCount = tr.patternScope.pattern_names.size(); 129 154 } 155 156 public void disassemble () 157 { 158 disassemble(OutPort.errDefault(), (Translator) Compilation.getCurrent(), 159 0, program.length()); 160 } 161 162 public void disassemble (java.io.PrintWriter ps, Translator tr) 163 { 164 disassemble(ps, tr, 0, program.length()); 165 } 166 167 void disassemble (java.io.PrintWriter ps, Translator tr, int start, int limit) 168 { 169 Vector pattern_names = null; 170 if (tr != null && tr.patternScope != null) 171 pattern_names = tr.patternScope.pattern_names; 172 int value = 0; 173 for (int i = start; i < limit; ) 174 { 175 char ch = program.charAt(i); 176 ps.print(" " + i + ": " + (int)ch); 177 i++; 178 int opcode = ch & 7; 179 value = (value << 13) | (ch >> 3); 180 switch (opcode) 181 { 182 case MATCH_WIDE: 183 ps.println(" - WIDE "+value); 184 continue; 185 case MATCH_EQUALS: 186 ps.print(" - EQUALS["+value+"]"); 187 if (literals != null && value >= 0 && value < literals.length) 188 ps.print(literals[value]); 189 ps.println(); 190 break; 191 case MATCH_ANY: 192 case MATCH_ANY_CAR: 193 ps.print((opcode == MATCH_ANY ? " - ANY[" : " - ANY_CAR[") 194 +value+"]"); 195 if (pattern_names != null 196 && value >= 0 && value < pattern_names.size()) 197 ps.print(pattern_names.elementAt(value)); 198 ps.println(); 199 break; 200 case MATCH_PAIR: 201 ps.println(" - PAIR["+value+"]"); 202 break; 203 case MATCH_LREPEAT: 204 ps.println(" - LREPEAT["+value+"]"); 205 disassemble(ps, tr, i, i+value); 206 i += value; 207 ps.println(" " + i + ": - repeat first var:"+(program.charAt(i++)>>3)); 208 ps.println(" " + i + ": - repeast nested vars:"+(program.charAt(i++)>>3)); 209 break; 210 case MATCH_LENGTH: 211 ps.println(" - LENGTH "+(value>>1)+" pairs. " 212 + (((value&1)==0?"pure list":"impure list"))); 213 break; 214 case MATCH_MISC: 215 ps.print("[misc ch:"+(int)ch+" n:"+(int)(MATCH_NIL)+"]"); 216 if (ch == MATCH_NIL) 217 { 218 ps.println(" - NIL"); 219 break; 220 } 221 if (ch == MATCH_VECTOR) 222 { 223 ps.println(" - VECTOR"); 224 break; 225 } 226 if (ch == MATCH_IGNORE) 227 { 228 ps.println(" - IGNORE"); 229 break; 230 } 231 default: 232 ps.println(" - "+opcode+'/'+value); 233 break; 234 } 235 value = 0; 236 } 237 } 238 239 240 241 244 void translate (Object pattern, StringBuffer program, 245 Object [] literal_identifiers, int nesting, 246 Vector literals, SyntaxForm syntax, 247 char context, 248 Translator tr) 249 { 250 PatternScope patternScope = tr.patternScope; 251 Vector patternNames = patternScope.pattern_names; 252 for (;;) 253 { 254 while (pattern instanceof SyntaxForm) 255 { 256 syntax = (SyntaxForm) pattern; 257 pattern = syntax.form; 258 } 259 if (pattern instanceof Pair) 260 { 261 Object savePos = tr.pushPositionOf(pattern); 262 try 263 { 264 int start_pc = program.length(); 265 program.append((char) MATCH_PAIR); 266 Pair pair = (Pair) pattern; 267 SyntaxForm car_syntax = syntax; 268 Object next = pair.cdr; 269 while (next instanceof SyntaxForm) 270 { 271 syntax = (SyntaxForm) next; 272 next = syntax.form; 273 } 274 boolean repeat = false; 275 if (next instanceof Pair 276 && tr.matches(((Pair) next).car, SyntaxRule.dots3)) 277 { 278 repeat = true; 279 next = ((Pair) next).cdr; 280 while (next instanceof SyntaxForm) 281 { 282 syntax = (SyntaxForm) next; 283 next = syntax.form; 284 } 285 } 286 287 int subvar0 = patternNames.size(); 288 if (context == 'P') 289 context = '\0'; 290 translate(pair.car, program, literal_identifiers, 291 repeat ? nesting + 1 : nesting, 292 literals, car_syntax, 293 context == 'V' ? '\0' : 'P', tr); 294 int subvarN = patternNames.size() - subvar0; 295 int width = ((program.length() - start_pc - 1) << 3) 296 | (repeat ? MATCH_LREPEAT : MATCH_PAIR); 297 if (width > 0xFFFF) 298 start_pc += insertInt(start_pc, program, 299 (width >> 13) + MATCH_WIDE); 300 program.setCharAt(start_pc, (char) width); 301 302 int restLength = Translator.listLength(next); 303 if (restLength == Integer.MIN_VALUE) 304 { 305 tr.syntaxError("cyclic pattern list"); 306 return; 307 } 308 309 if (repeat) 310 { 311 addInt(program, subvar0 << 3); 312 addInt(program, subvarN << 3); 313 if (next == LList.Empty) 314 { 315 program.append((char) MATCH_NIL); 316 return; 317 } 318 else 319 { 320 restLength = restLength >= 0 ? restLength << 1 322 : ((-restLength) << 1) - 1; 323 addInt(program, (restLength << 3) | MATCH_LENGTH); 324 } 325 } 326 327 pattern = next; 328 continue; 329 } 330 finally 331 { 332 tr.popPositionOf(savePos); 333 } 334 } 335 else if (pattern instanceof String || pattern instanceof Symbol) 336 { 337 for (int j = literal_identifiers.length; --j >= 0; ) 338 { 339 ScopeExp scope = syntax == null ? tr.currentScope() 340 : syntax.scope; 341 if (literalIdentifierEq(pattern, scope, 342 literal_identifiers[j])) 343 { 344 int i = SyntaxTemplate.indexOf(literals, pattern); 345 if (i < 0) 346 { 347 i = literals.size(); 348 literals.addElement(pattern); 349 } 350 addInt(program, (i << 3) | MATCH_EQUALS); 351 return; 352 } 353 } 354 if (patternNames.contains(pattern)) 355 tr.syntaxError("duplicated pattern variable " + pattern); 356 int i = patternNames.size(); 357 patternNames.addElement(pattern); 358 boolean matchCar = context == 'P'; 359 int n = (nesting << 1) + (matchCar ? 1 : 0); 360 patternScope.patternNesting.append((char) n); 361 Declaration decl = patternScope.addDeclaration(pattern); 362 decl.setLocation(tr); 363 tr.push(decl); 364 addInt(program, (i << 3) | (matchCar ? MATCH_ANY_CAR : MATCH_ANY)); 365 return; 366 } 367 else if (pattern == LList.Empty) 368 { 369 program.append((char) MATCH_NIL); 370 return; 371 } 372 else if (pattern instanceof FVector) 373 { 374 program.append((char) MATCH_VECTOR); 375 pattern = LList.makeList((FVector) pattern); 376 context = 'V'; 377 continue; 378 } 379 else 380 { 381 int i = SyntaxTemplate.indexOf(literals, pattern); 382 if (i < 0) 383 { 384 i = literals.size(); 385 literals.addElement(pattern); 386 } 387 addInt(program, (i << 3) | MATCH_EQUALS); 388 return; 389 } 390 } 391 } 392 393 private static void addInt (StringBuffer sbuf, int val) 394 { 395 if (val > 0xFFFF) 396 addInt(sbuf, (val << 13) + MATCH_WIDE); 397 sbuf.append((char) (val)); 398 } 399 400 private static int insertInt (int offset, StringBuffer sbuf, int val) 401 { 402 if (val > 0xFFFF) 403 offset += insertInt(offset, sbuf, (val << 13) + MATCH_WIDE); 404 sbuf.insert(offset, (char) (val)); 405 return offset+1; 406 } 407 408 412 boolean match_car (Pair p, Object [] vars, int start_vars, 413 int pc, SyntaxForm syntax) 414 { 415 int pc_start = pc; 416 char ch; 417 int value = (ch = program.charAt(pc++)) >> 3; 418 while ((ch & 7) == MATCH_WIDE) 419 value = (value << 13) | ((ch = program.charAt(pc++)) >> 3); 420 if ((ch & 7) == MATCH_ANY_CAR) 421 { 422 if (syntax != null && ! (p.car instanceof SyntaxForm)) 423 p = Translator.makePair(p, syntax.fromDatum(p.car), p.cdr); 424 vars[start_vars + value] = p; 425 return true; 426 } 427 return match (p.car, vars, start_vars, pc_start, syntax); 428 } 429 430 public boolean match (Object obj, Object [] vars, int start_vars, 431 int pc, SyntaxForm syntax) 432 { 433 int value = 0; 434 Pair p; 435 for (;;) 436 { 437 while (obj instanceof SyntaxForm) 438 { 439 syntax = (SyntaxForm) obj; 440 obj = syntax.form; 441 } 442 char ch = program.charAt(pc++); 443 int opcode = ch & 7; 444 value = (value << 13) | (ch >> 3); 445 switch (opcode) 446 { 447 case MATCH_WIDE: 448 continue; 449 case MATCH_MISC: 450 if (ch == MATCH_NIL) 451 return obj == LList.Empty; 452 else if (ch == MATCH_VECTOR) 453 { 454 if (! (obj instanceof FVector)) 455 return false; 456 return match(LList.makeList((FVector) obj), 457 vars, start_vars, pc, syntax); 458 } 459 else if (ch == MATCH_IGNORE) 460 return true; 461 else 462 throw new Error ("unknwon pattern opcode"); 463 case MATCH_NIL: 464 return obj == LList.Empty; 465 case MATCH_LENGTH: 466 int npairs = value>>1; 467 Object o = obj; 468 for (int i = 0;;i++) 469 { 470 while (o instanceof SyntaxForm) 471 o = ((SyntaxForm) o).form; 472 if (i == npairs) 473 { 474 if ((value&1) == 0 ? o != LList.Empty : o instanceof Pair) 475 return false; 476 break; 477 } 478 else if (o instanceof Pair) 479 o = ((Pair) o).cdr; 480 else 481 return false; 482 } 483 value = 0; 484 continue; 485 case MATCH_PAIR: 486 if (! (obj instanceof Pair)) 487 return false; 488 p = (Pair) obj; 489 if (! match_car(p, vars, start_vars, pc, syntax)) 490 return false; 491 pc += value; 492 value = 0; 493 obj = p.cdr; 494 continue; 495 case MATCH_LREPEAT: 496 int repeat_pc = pc; 497 pc += value; 498 int subvar0 = (ch = program.charAt(pc++)) >> 3; 499 while ((ch & 0x7) == MATCH_WIDE) 500 subvar0 = (subvar0 << 13) | ((ch = program.charAt(pc++)) >> 3); 501 subvar0 += start_vars; 502 int subvarN = program.charAt(pc++) >> 3; 503 while ((ch & 0x7) == MATCH_WIDE) 504 subvarN = (subvarN << 13) | ((ch = program.charAt(pc++)) >> 3); 505 506 ch = program.charAt(pc++); 507 boolean listRequired = true; 508 int pairsRequired; 509 if (ch == MATCH_NIL) 510 { 511 pairsRequired = 0; 512 } 513 else 514 { 515 value = ch >> 3; 516 while ((ch & 0x7) == MATCH_WIDE) 517 value = (value << 13) | ((ch = program.charAt(pc++)) >> 3); 518 if ((value & 1) != 0) 519 listRequired = false; 520 pairsRequired = value >> 1; 521 } 522 int pairsValue = Translator.listLength(obj); 523 boolean listValue; 524 525 if (pairsValue >= 0) 526 listValue = true; 527 else 528 { 529 listValue = false; 530 pairsValue = -1-pairsValue; 531 } 532 if (pairsValue < pairsRequired || (listRequired && ! listValue)) 533 return false; 534 int repeat_count = pairsValue - pairsRequired; 535 Object [][] arrays = new Object [subvarN][]; 536 537 for (int j = 0; j < subvarN; j++) 538 arrays[j] = new Object [repeat_count]; 539 for (int i = 0; i < repeat_count; i++) 540 { 541 while (obj instanceof SyntaxForm) 542 { 543 syntax = (SyntaxForm) obj; 544 obj = syntax.form; 545 } 546 p = (Pair) obj; 547 if (! match_car (p, vars, start_vars, repeat_pc, syntax)) 548 return false; 549 obj = p.cdr; 550 for (int j = 0; j < subvarN; j++) 551 arrays[j][i] = vars[subvar0+j]; 552 } 553 for (int j = 0; j < subvarN; j++) 554 vars[subvar0+j] = arrays[j]; 555 value = 0; 556 if (pairsRequired == 0 && listRequired) 557 return true; 558 continue; 559 case MATCH_EQUALS: 560 Object lit = literals[value]; 561 if (lit instanceof String && obj instanceof Symbol) 564 obj = ((Symbol) obj).getName(); 565 return lit.equals(obj); 566 case MATCH_ANY: 567 if (syntax != null) 568 obj = syntax.fromDatum(obj); 569 vars[start_vars + value] = obj; 570 return true; 571 case MATCH_ANY_CAR: default: 573 disassemble(); 574 throw new Error ("unrecognized pattern opcode @pc:"+pc); 575 } 576 } 577 } 578 579 public void writeExternal(ObjectOutput out) throws IOException 580 { 581 out.writeObject(program); 582 out.writeObject(literals); 583 out.writeInt(varCount); 584 } 585 586 public void readExternal(ObjectInput in) 587 throws IOException, ClassNotFoundException 588 { 589 literals = (Object []) in.readObject(); 590 program = (String ) in.readObject(); 591 varCount = in.readInt(); 592 } 593 594 595 public static Object [] allocVars (int varCount, Object [] outer) 596 { 597 Object [] vars = new Object [varCount]; 598 if (outer != null) 599 System.arraycopy(outer, 0, vars, 0, outer.length); 600 return vars; 601 } 602 603 public static boolean literalIdentifierEq (Object id1, ScopeExp sc1, 604 Object literal2) 605 { 606 if (literal2 instanceof SyntaxForm) 607 { 608 SyntaxForm syntax = (SyntaxForm) literal2; 609 return literalIdentifierEq(id1, sc1, syntax.form, syntax.scope); 610 } 611 return literalIdentifierEq(id1, sc1, literal2, null); 612 } 613 614 public static boolean literalIdentifierEq (Object id1, ScopeExp sc1, 615 Object id2, ScopeExp sc2) 616 { 617 if (id1 != id2) 618 return false; 619 Declaration d1 = null, d2 = null; 620 while (sc1 != null && ! (sc1 instanceof ModuleExp)) 621 { 622 d1 = sc1.lookup(id1); 623 if (d1 != null) 624 break; 625 sc1 = sc1.outer; 626 } 627 while (sc2 != null && ! (sc2 instanceof ModuleExp)) 628 { 629 d2 = sc1.lookup(id1); 630 if (d2 != null) 631 break; 632 sc2 = sc2.outer; 633 } 634 return d1 == d2; 635 } 636 637 638 public static Object [] getLiteralsList (Object list, 639 SyntaxForm syntax, Translator tr) 640 { 641 Object savePos = tr.pushPositionOf(list); 642 int count = Translator.listLength(list); 643 if (count < 0) 644 { 645 tr.error('e', "missing or malformed literals list"); 646 count = 0; 647 } 648 Object [] literals = new Object [count + 1]; 649 for (int i = 1; i <= count; i++) 650 { 651 while (list instanceof SyntaxForm) 652 { 653 syntax = (SyntaxForm) list; 654 list = syntax.form; 655 } 656 Pair pair = (Pair) list; 657 tr.pushPositionOf(pair); 658 Object literal = pair.car; 659 Object wrapped; 660 if (literal instanceof SyntaxForm) 661 { 662 wrapped = literal; 663 literal = (( SyntaxForm) literal).form; 664 } 665 else 666 wrapped = literal; if (! (literal instanceof String 668 || literal instanceof gnu.mapping.Symbol)) 669 tr.error('e', "non-symbol '"+literal+"' in literals list"); 670 literals[i] = wrapped; 671 list = pair.cdr; 672 } 673 tr.popPositionOf(savePos); 674 return literals; 675 } 676 677 public void print (Consumer out) 678 { 679 out.write("#<syntax-pattern>"); 680 } 681 } 682 | Popular Tags |