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