1 /* 2 * Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package jdk.incubator.code.extern; 27 28 import java.io.IOException; 29 import java.io.InputStream; 30 import jdk.incubator.code.*; 31 import jdk.incubator.code.dialect.core.CoreOp; 32 import jdk.incubator.code.dialect.core.CoreType; 33 import jdk.incubator.code.dialect.java.JavaOp; 34 import jdk.incubator.code.extern.impl.Tokens.TokenKind; 35 import jdk.incubator.code.extern.impl.DescParser; 36 import jdk.incubator.code.extern.impl.Lexer; 37 import jdk.incubator.code.extern.impl.Scanner; 38 import jdk.incubator.code.extern.impl.Tokens; 39 import jdk.incubator.code.dialect.java.JavaType; 40 import jdk.incubator.code.dialect.java.impl.JavaTypeUtils; 41 42 import java.nio.charset.StandardCharsets; 43 import java.util.ArrayList; 44 import java.util.HashMap; 45 import java.util.List; 46 import java.util.Map; 47 48 /** 49 * A parser of serialized code models from their textual form. 50 * <p> 51 * The syntactic grammar of a code mode is specified in the grammar notation, and is a subset of the grammar, 52 * specified by the JLS, see section 2.4. (Except that we cannot express non-terminal symbols in italic type.) 53 * <p> 54 * {@snippet lang=text : 55 * Operation: 56 * [Value =] Name {Operands} {Successors} {Attributes} {Bodies} ; 57 * 58 * Operands: 59 * ValueIdentifier {ValueIdentifier} 60 * 61 * Successors: 62 * Successor {Successor} 63 * 64 * Successor: 65 * BlockIdentifier 66 * BlockIdentifier () 67 * BlockIdentifier ( ValueIdentifier {, ValueIdentifier} ) 68 * 69 * Attributes: 70 * Attribute {Attribute} 71 * 72 * Attribute: 73 * @ AttributeValue 74 * @ Name = AttributeValue 75 * 76 * AttributeValue: 77 * ExType 78 * NumericAttributeValue 79 * BooleanLiteral 80 * CharacterLiteral 81 * StringLiteral 82 * NullLiteral 83 * 84 * NumericAttributeValue: 85 * [ '-' ] IntLiteral 86 * [ '-' ] LongLiteral 87 * [ '-' ] FloatLiteral 88 * [ '-' ] DoubleLiteral 89 * 90 * Bodies: 91 * Body {Body} 92 * 93 * Body: 94 * BlockIdentifier ( ) Type -> { Operations {Block} } 95 * BlockIdentifier ( Value {, Value} ) Type -> { Operations {Block} } 96 * 97 * Operations: 98 * Operation {Operation} 99 * 100 * Block: 101 * BlockIdentifier : Operations 102 * BlockIdentifier ( ) : Operations 103 * BlockIdentifier ( Value {, Value} ) : Operations 104 * 105 * BlockIdentifier: 106 * ^ Identifier 107 * 108 * Value: 109 * ValueIdentifier : Type 110 * 111 * ValueIdentifier: 112 * % JavaLetterOrDigit {JavaLetterOrDigit} 113 * 114 * Name: 115 * Identifier 116 * Name . Identifier 117 * 118 * Type: 119 * same as in section 4.1 of JLS but without any annotations 120 * 121 * Identifier: 122 * same as in section 3 of JLS 123 * 124 * JavaLetterOrDigit: 125 * same as in section 3 of JLS 126 * 127 * StringLiteral: 128 * same as in section 3 of JLS 129 * 130 * NullLiteral: 131 * same as in section 3 of JLS 132 * } 133 */ 134 public final class OpParser { 135 136 static final ExternalizedTypeElement VOID = JavaType.VOID.externalize(); 137 138 // @@@ check failure from operation and type element factories 139 140 /** 141 * Parse a code model from its serialized textual form obtained from an input stream. 142 * 143 * @param factory the dialect factory used to construct operations and type elements. 144 * @param in the input stream 145 * @return the list of operations 146 * @throws IOException if parsing fails to read from the input stream 147 * @throws IllegalArgumentException if parsing fails 148 */ 149 public static List<Op> fromStream(DialectFactory factory, InputStream in) throws IOException { 150 String s = new String(in.readAllBytes(), StandardCharsets.UTF_8); 151 return fromString(factory, s); 152 } 153 154 /** 155 * Parse a code model from its serialized textual form obtained from an input string. 156 * 157 * @param factory the dialect factory used to construct operations and type elements. 158 * @param in the input string 159 * @return the list of operations 160 * @throws IllegalArgumentException if parsing fails 161 */ 162 public static List<Op> fromString(DialectFactory factory, String in) { 163 return parse(factory.opFactory(), factory.typeElementFactory(), in); 164 } 165 166 /** 167 * Parse a Java code model, modeling a method body or quoted lambda body, from 168 * its serialized textual form obtained from an input string. 169 * <p> 170 * This method uses the Java {@link JavaOp#JAVA_DIALECT_FACTORY dialect factory} 171 * for construction of operations and type elements. 172 * 173 * @param in the input string 174 * @return the code model 175 * @throws IllegalArgumentException if parsing fails or if top-level operation 176 * of the code model is not an instance of {@link CoreOp.FuncOp} 177 */ 178 public static Op fromStringOfJavaCodeModel(String in) { 179 // @@@ Used produce code models stored as text in the class file, 180 // can eventually be removed as storing text is now a backup option. 181 Op op = fromString(JavaOp.JAVA_DIALECT_FACTORY, in).get(0); 182 if (!(op instanceof CoreOp.FuncOp)) { 183 throw new IllegalArgumentException("Op is not a FuncOp: " + op); 184 } 185 return op; 186 } 187 188 static List<Op> parse(OpFactory opFactory, TypeElementFactory typeFactory, String in) { 189 Lexer lexer = Scanner.factory().newScanner(in); 190 lexer.nextToken(); 191 192 List<OpNode> opNodes = new OpParser(lexer).parseNodes(); 193 194 Context c = new Context(opFactory, typeFactory); 195 return opNodes.stream().map(n -> nodeToOp(n, VOID, c, null)).toList(); 196 } 197 198 199 static final class Context { 200 final Context parent; 201 final OpFactory opFactory; 202 final TypeElementFactory typeFactory; 203 final Map<String, Value> valueMap; 204 final Map<String, Block.Builder> blockMap; 205 206 Context(Context that, boolean isolated) { 207 this.parent = that; 208 this.opFactory = that.opFactory; 209 this.typeFactory = that.typeFactory; 210 this.valueMap = isolated ? new HashMap<>() : new HashMap<>(that.valueMap); 211 this.blockMap = new HashMap<>(); 212 } 213 214 Context(OpFactory opFactory, TypeElementFactory typeFactory) { 215 this.parent = null; 216 this.opFactory = opFactory; 217 this.typeFactory = typeFactory; 218 this.valueMap = new HashMap<>(); 219 this.blockMap = new HashMap<>(); 220 } 221 222 Context fork(boolean isolated) { 223 return new Context(this, isolated); 224 } 225 226 void putValue(String name, Value opr) { 227 valueMap.put(name, opr); 228 } 229 230 Value getValue(String name) { 231 Value value = valueMap.get(name); 232 if (value == null) { 233 // @@@ location 234 throw new IllegalArgumentException("Undeclared value referenced: " + name); 235 } 236 237 return value; 238 } 239 240 void putBlock(String name, Block.Builder bm) { 241 blockMap.put(name, bm); 242 } 243 244 Block.Builder getBlock(String name) { 245 Block.Builder block = blockMap.get(name); 246 if (block == null) { 247 // @@@ location 248 throw new IllegalArgumentException("Undeclared block referenced: " + name); 249 } 250 251 return block; 252 } 253 } 254 255 static Op nodeToOp(OpNode opNode, ExternalizedTypeElement rtype, Context c, Body.Builder ancestorBody) { 256 ExternalizedOp opdef = nodeToOpDef(opNode, rtype, c, ancestorBody); 257 return c.opFactory.constructOpOrFail(opdef); 258 } 259 260 static ExternalizedOp nodeToOpDef(OpNode opNode, ExternalizedTypeElement rtype, Context c, Body.Builder ancestorBody) { 261 String operationName = opNode.name; 262 List<Value> operands = opNode.operands.stream().map(c::getValue).toList(); 263 List<Block.Reference> successors = opNode.successors.stream() 264 .map(n -> nodeToSuccessor(n, c)).toList(); 265 List<Body.Builder> bodies = opNode.bodies.stream() 266 .map(n -> nodeToBody(n, c.fork(false), ancestorBody)).toList(); 267 Location location = null; 268 if (!opNode.attributes.isEmpty()) { 269 Object v = opNode.attributes.remove(OpWriter.ATTRIBUTE_LOCATION); 270 location = switch (v) { 271 case String s -> Location.fromString(s); 272 case Location loc -> loc; 273 case null -> null; 274 default -> throw new UnsupportedOperationException("Unsupported location value:" + v); 275 }; 276 } 277 return new ExternalizedOp(operationName, 278 location, 279 operands, 280 successors, 281 c.typeFactory.constructType(rtype), 282 inflateAttributes(opNode.attributes, c.typeFactory), 283 bodies); 284 } 285 286 static Map<String, Object> inflateAttributes(Map<String, Object> attributes, TypeElementFactory typeFactory) { 287 Map<String, Object> newAttributes = new HashMap<>(); 288 for (Map.Entry<String, Object> e : attributes.entrySet()) { 289 String name = e.getKey(); 290 Object value = e.getValue(); 291 if (value instanceof ExternalizedTypeElement ete) { 292 value = typeFactory.constructType(JavaTypeUtils.inflate(ete)); 293 } 294 newAttributes.put(name, value); 295 } 296 return newAttributes; 297 } 298 299 static Body.Builder nodeToBody(BodyNode n, Context c, Body.Builder ancestorBody) { 300 Body.Builder body = Body.Builder.of(ancestorBody, 301 // Create function type with just the return type and add parameters afterward 302 CoreType.functionType(c.typeFactory.constructType(n.rtype))); 303 Block.Builder eb = body.entryBlock(); 304 305 // Create blocks upfront for forward referencing successors 306 for (int i = 0; i < n.blocks.size(); i++) { 307 BlockNode bn = n.blocks.get(i); 308 Block.Builder b; 309 if (i == 0) { 310 b = body.entryBlock(); 311 } else { 312 b = eb.block(); 313 c.putBlock(bn.name, b); 314 } 315 316 for (ValueNode a : bn.parameters) { 317 Block.Parameter v = b.parameter(c.typeFactory.constructType(a.type)); 318 c.putValue(a.name, v); 319 } 320 } 321 322 // Create operations 323 for (int i = 0; i < n.blocks.size(); i++) { 324 BlockNode bn = n.blocks.get(i); 325 Block.Builder b; 326 if (i == 0) { 327 b = body.entryBlock(); 328 } else { 329 b = c.getBlock(n.blocks.get(i).name); 330 } 331 332 for (OpNode on : bn.ops) { 333 ValueNode r = on.result; 334 if (r != null) { 335 Op.Result v = b.op(nodeToOp(on, r.type, c, body)); 336 c.putValue(r.name, v); 337 } else { 338 b.op(nodeToOp(on, VOID, c, body)); 339 } 340 } 341 } 342 343 return body; 344 } 345 346 static Block.Reference nodeToSuccessor(SuccessorNode n, Context c) { 347 return c.getBlock(n.blockName).successor(n.arguments().stream().map(c::getValue).toList()); 348 } 349 350 // @@@ Add tokens to access position of nodes on error 351 352 record OpNode(ValueNode result, 353 String name, 354 List<String> operands, 355 List<SuccessorNode> successors, 356 Map<String, Object> attributes, 357 List<BodyNode> bodies) { 358 } 359 360 record SuccessorNode(String blockName, 361 List<String> arguments) { 362 } 363 364 record BodyNode(ExternalizedTypeElement rtype, 365 List<BlockNode> blocks) { 366 } 367 368 record BlockNode(String name, 369 List<ValueNode> parameters, 370 List<OpNode> ops) { 371 } 372 373 record ValueNode(String name, 374 ExternalizedTypeElement type) { 375 } 376 377 final Lexer lexer; 378 379 OpParser(Lexer lexer) { 380 this.lexer = lexer; 381 } 382 383 List<OpNode> parseNodes() { 384 List<OpNode> ops = new ArrayList<>(); 385 while (lexer.token().kind != Tokens.TokenKind.EOF) { 386 ops.add(parseOperation()); 387 } 388 return ops; 389 } 390 391 OpNode parseOperation() { 392 ValueNode operationResult; 393 if (lexer.is(Tokens.TokenKind.VALUE_IDENTIFIER)) { 394 operationResult = parseValueNode(); 395 lexer.accept(Tokens.TokenKind.EQ); 396 } else { 397 operationResult = null; 398 } 399 400 String operationName = parseName(); 401 402 // Operands 403 final List<String> operands; 404 if (lexer.is(Tokens.TokenKind.VALUE_IDENTIFIER)) { 405 operands = parseOperands(); 406 } else { 407 operands = List.of(); 408 } 409 410 // Successors 411 // ^name(%x, %d) 412 final List<SuccessorNode> successors; 413 if (lexer.is(Tokens.TokenKind.CARET)) { 414 successors = parseSuccessors(); 415 } else { 416 successors = List.of(); 417 } 418 419 // Attributes 420 final Map<String, Object> attributes; 421 if (lexer.is(Tokens.TokenKind.MONKEYS_AT)) { 422 attributes = parseAttributes(); 423 } else { 424 attributes = Map.of(); 425 } 426 427 // Bodies 428 List<BodyNode> bodies; 429 if (lexer.is(Tokens.TokenKind.CARET) || lexer.is(Tokens.TokenKind.LPAREN)) { 430 bodies = parseBodies(); 431 } else { 432 bodies = List.of(); 433 } 434 435 lexer.accept(Tokens.TokenKind.SEMI); 436 437 return new OpNode(operationResult, operationName, operands, successors, attributes, bodies); 438 } 439 440 Map<String, Object> parseAttributes() { 441 Map<String, Object> attributes = new HashMap<>(); 442 while (lexer.acceptIf(Tokens.TokenKind.MONKEYS_AT)) { 443 String attributeName; 444 if (isNameStart()) { 445 attributeName = parseName(); 446 lexer.accept(Tokens.TokenKind.EQ); 447 } else { 448 attributeName = ""; 449 } 450 Object attributeValue = parseAttributeValue(); 451 attributes.put(attributeName, attributeValue); 452 } 453 return attributes; 454 } 455 456 boolean isNameStart() { 457 // we need to lookahead to see if we can find an identifier followed by a '=', 458 // in which case we know what we're looking at is an attribute name 459 int curr = 0; 460 while (true) { 461 if (lexer.token(curr++).kind != TokenKind.IDENTIFIER) { 462 return false; 463 } 464 TokenKind next = lexer.token(curr++).kind; 465 if (next == TokenKind.EQ) { 466 return true; 467 } else if (next != TokenKind.DOT) { 468 return false; 469 } 470 } 471 } 472 473 Object parseAttributeValue() { 474 if (lexer.is(Tokens.TokenKind.IDENTIFIER)) { 475 return DescParser.parseExTypeElem(lexer); 476 } 477 478 Object value = parseLiteral(lexer.token()); 479 lexer.nextToken(); 480 481 return value; 482 } 483 484 Object parseLiteral(Tokens.Token t) { 485 return switch (t.kind) { 486 case STRINGLITERAL -> t.stringVal(); 487 case NULL -> ExternalizedOp.NULL_ATTRIBUTE_VALUE; 488 case CHARLITERAL -> t.stringVal().charAt(0); 489 case TRUE -> true; 490 case FALSE -> false; 491 default -> parseNumericLiteral(t); 492 }; 493 } 494 495 Object parseNumericLiteral(Tokens.Token t) { 496 String minusOpt = ""; 497 if (t.kind == TokenKind.SUB) { 498 minusOpt = "-"; 499 lexer.nextToken(); 500 t = lexer.token(); 501 } 502 return switch (t.kind) { 503 case INTLITERAL -> Integer.valueOf(minusOpt + t.stringVal()); 504 case LONGLITERAL -> Long.valueOf(minusOpt + t.stringVal()); 505 case FLOATLITERAL -> Float.valueOf(minusOpt + t.stringVal()); 506 case DOUBLELITERAL -> Double.valueOf(minusOpt + t.stringVal()); 507 default -> throw lexer.unexpected(); 508 }; 509 } 510 511 List<String> parseOperands() { 512 List<String> operands = new ArrayList<>(); 513 while (lexer.is(Tokens.TokenKind.VALUE_IDENTIFIER)) { 514 operands.add(lexer.token().name().substring(1)); 515 lexer.nextToken(); 516 } 517 return operands; 518 } 519 520 List<SuccessorNode> parseSuccessors() { 521 List<SuccessorNode> successors = new ArrayList<>(); 522 523 while (lexer.is(Tokens.TokenKind.CARET) && !isBody()) { 524 lexer.nextToken(); 525 successors.add(parseSuccessor()); 526 } 527 528 return successors; 529 } 530 531 // Lookahead from "^" to determine if Body 532 boolean isBody() { 533 assert lexer.is(Tokens.TokenKind.CARET); 534 535 int pos = 1; 536 lexer.token(pos++); 537 assert lexer.token(1).kind == Tokens.TokenKind.IDENTIFIER; 538 539 if (lexer.token(pos++).kind != Tokens.TokenKind.LPAREN) { 540 return false; 541 } 542 543 Tokens.Token t; 544 while ((t = lexer.token(pos++)).kind != Tokens.TokenKind.RPAREN) { 545 if (t.kind == Tokens.TokenKind.EOF) { 546 return false; 547 } else if (t.kind == Tokens.TokenKind.COLON) { 548 // Encountered Value 549 return true; 550 } 551 } 552 553 // Encountered return type 554 return lexer.token(pos++).kind == Tokens.TokenKind.IDENTIFIER; 555 } 556 557 SuccessorNode parseSuccessor() { 558 String blockName = lexer.accept(Tokens.TokenKind.IDENTIFIER).name(); 559 560 List<String> arguments = new ArrayList<>(); 561 if (lexer.acceptIf(Tokens.TokenKind.LPAREN) && !lexer.acceptIf(Tokens.TokenKind.RPAREN)) { 562 do { 563 arguments.add(lexer.accept(Tokens.TokenKind.VALUE_IDENTIFIER).name().substring(1)); 564 } while (lexer.acceptIf(Tokens.TokenKind.COMMA)); 565 lexer.accept(Tokens.TokenKind.RPAREN); 566 } 567 568 return new SuccessorNode(blockName, arguments); 569 } 570 571 List<BodyNode> parseBodies() { 572 List<BodyNode> bodies = new ArrayList<>(); 573 while (lexer.is(Tokens.TokenKind.CARET) || lexer.is(Tokens.TokenKind.LPAREN)) { 574 BodyNode body = parseBody(); 575 bodies.add(body); 576 } 577 return bodies; 578 } 579 580 BodyNode parseBody() { 581 // Body name 582 final String bodyName; 583 if (lexer.acceptIf(Tokens.TokenKind.CARET)) { 584 bodyName = lexer.accept(Tokens.TokenKind.IDENTIFIER).name(); 585 } else { 586 bodyName = null; 587 } 588 589 // Entry block header 590 List<ValueNode> arguments = parseBlockHeaderArguments(true); 591 // Body return type 592 ExternalizedTypeElement rtype = parseExTypeElem(); 593 594 lexer.accept(Tokens.TokenKind.ARROW); 595 lexer.accept(Tokens.TokenKind.LBRACE); 596 597 List<BlockNode> blocks = parseBlocks(bodyName, arguments); 598 599 lexer.accept(Tokens.TokenKind.RBRACE); 600 601 return new BodyNode(rtype, blocks); 602 } 603 604 List<ValueNode> parseBlockHeaderArguments(boolean isEntryBlock) { 605 boolean parseArguments; 606 if (isEntryBlock) { 607 lexer.accept(Tokens.TokenKind.LPAREN); 608 parseArguments = true; 609 } else { 610 parseArguments = lexer.acceptIf(Tokens.TokenKind.LPAREN); 611 } 612 if (!parseArguments || lexer.acceptIf(Tokens.TokenKind.RPAREN)) { 613 return new ArrayList<>(); 614 } 615 616 List<ValueNode> arguments = new ArrayList<>(); 617 do { 618 arguments.add(parseValueNode()); 619 } while (lexer.acceptIf(Tokens.TokenKind.COMMA)); 620 lexer.accept(Tokens.TokenKind.RPAREN); 621 622 return arguments; 623 } 624 625 ValueNode parseValueNode() { 626 String valueName = lexer.accept(Tokens.TokenKind.VALUE_IDENTIFIER).name().substring(1); 627 628 lexer.accept(Tokens.TokenKind.COLON); 629 630 ExternalizedTypeElement type = parseExTypeElem(); 631 632 return new ValueNode(valueName, type); 633 } 634 635 List<BlockNode> parseBlocks(String entryBlockName, List<ValueNode> entryBlockArguments) { 636 List<BlockNode> blocks = new ArrayList<>(); 637 638 // Entry block ops 639 BlockNode entryBlock = new BlockNode(entryBlockName, entryBlockArguments, parseOperations()); 640 blocks.add(entryBlock); 641 642 // Subsequent blocks 643 while (lexer.acceptIf(Tokens.TokenKind.CARET)) { 644 String blockName = lexer.accept(Tokens.TokenKind.IDENTIFIER).name(); 645 List<ValueNode> blockArguments = parseBlockHeaderArguments(false); 646 647 lexer.accept(Tokens.TokenKind.COLON); 648 649 BlockNode block = new BlockNode(blockName, blockArguments, parseOperations()); 650 blocks.add(block); 651 } 652 653 return blocks; 654 } 655 656 List<OpNode> parseOperations() { 657 List<OpNode> ops = new ArrayList<>(); 658 while (lexer.is(Tokens.TokenKind.MONKEYS_AT) || lexer.is(Tokens.TokenKind.VALUE_IDENTIFIER) || lexer.is(Tokens.TokenKind.IDENTIFIER)) { 659 OpNode op = parseOperation(); 660 ops.add(op); 661 } 662 return ops; 663 } 664 665 String parseName() { 666 Tokens.Token t = lexer.accept(Tokens.TokenKind.IDENTIFIER); 667 StringBuilder name = new StringBuilder(); 668 name.append(t.name()); 669 while (lexer.acceptIf(Tokens.TokenKind.DOT)) { 670 name.append(Tokens.TokenKind.DOT.name); 671 t = lexer.accept(Tokens.TokenKind.IDENTIFIER); 672 name.append(t.name()); 673 } 674 return name.toString(); 675 } 676 677 ExternalizedTypeElement parseExTypeElem() { 678 return JavaTypeUtils.inflate(DescParser.parseExTypeElem(lexer)); 679 } 680 } 681