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 Op.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 -> parseLocation(s);
272 case Op.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 Op.Location parseLocation(String s) {
287 String[] split = s.split(":", 3);
288 if (split.length < 2) {
289 throw new IllegalArgumentException();
290 }
291
292 int line = Integer.parseInt(split[0]);
293 int column = Integer.parseInt(split[1]);
294 String sourceRef;
295 if (split.length == 3) {
296 sourceRef = split[2];
297 } else {
298 sourceRef = null;
299 }
300 return new Op.Location(sourceRef, line, column);
301 }
302
303 static Map<String, Object> inflateAttributes(Map<String, Object> attributes, TypeElementFactory typeFactory) {
304 Map<String, Object> newAttributes = new HashMap<>();
305 for (Map.Entry<String, Object> e : attributes.entrySet()) {
306 String name = e.getKey();
307 Object value = e.getValue();
308 if (value instanceof ExternalizedTypeElement ete) {
309 value = typeFactory.constructType(JavaTypeUtils.inflate(ete));
310 }
311 newAttributes.put(name, value);
312 }
313 return newAttributes;
314 }
315
316 static Body.Builder nodeToBody(BodyNode n, Context c, Body.Builder ancestorBody) {
317 Body.Builder body = Body.Builder.of(ancestorBody,
318 // Create function type with just the return type and add parameters afterward
319 CoreType.functionType(c.typeFactory.constructType(n.rtype)));
320 Block.Builder eb = body.entryBlock();
321
322 // Create blocks upfront for forward referencing successors
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 = eb.block();
330 c.putBlock(bn.name, b);
331 }
332
333 for (ValueNode a : bn.parameters) {
334 Block.Parameter v = b.parameter(c.typeFactory.constructType(a.type));
335 c.putValue(a.name, v);
336 }
337 }
338
339 // Create operations
340 for (int i = 0; i < n.blocks.size(); i++) {
341 BlockNode bn = n.blocks.get(i);
342 Block.Builder b;
343 if (i == 0) {
344 b = body.entryBlock();
345 } else {
346 b = c.getBlock(n.blocks.get(i).name);
347 }
348
349 for (OpNode on : bn.ops) {
350 ValueNode r = on.result;
351 if (r != null) {
352 Op.Result v = b.op(nodeToOp(on, r.type, c, body));
353 c.putValue(r.name, v);
354 } else {
355 b.op(nodeToOp(on, VOID, c, body));
356 }
357 }
358 }
359
360 return body;
361 }
362
363 static Block.Reference nodeToSuccessor(SuccessorNode n, Context c) {
364 return c.getBlock(n.blockName).successor(n.arguments().stream().map(c::getValue).toList());
365 }
366
367 // @@@ Add tokens to access position of nodes on error
368
369 record OpNode(ValueNode result,
370 String name,
371 List<String> operands,
372 List<SuccessorNode> successors,
373 Map<String, Object> attributes,
374 List<BodyNode> bodies) {
375 }
376
377 record SuccessorNode(String blockName,
378 List<String> arguments) {
379 }
380
381 record BodyNode(ExternalizedTypeElement rtype,
382 List<BlockNode> blocks) {
383 }
384
385 record BlockNode(String name,
386 List<ValueNode> parameters,
387 List<OpNode> ops) {
388 }
389
390 record ValueNode(String name,
391 ExternalizedTypeElement type) {
392 }
393
394 final Lexer lexer;
395
396 OpParser(Lexer lexer) {
397 this.lexer = lexer;
398 }
399
400 List<OpNode> parseNodes() {
401 List<OpNode> ops = new ArrayList<>();
402 while (lexer.token().kind != Tokens.TokenKind.EOF) {
403 ops.add(parseOperation());
404 }
405 return ops;
406 }
407
408 OpNode parseOperation() {
409 ValueNode operationResult;
410 if (lexer.is(Tokens.TokenKind.VALUE_IDENTIFIER)) {
411 operationResult = parseValueNode();
412 lexer.accept(Tokens.TokenKind.EQ);
413 } else {
414 operationResult = null;
415 }
416
417 String operationName = parseName();
418
419 // Operands
420 final List<String> operands;
421 if (lexer.is(Tokens.TokenKind.VALUE_IDENTIFIER)) {
422 operands = parseOperands();
423 } else {
424 operands = List.of();
425 }
426
427 // Successors
428 // ^name(%x, %d)
429 final List<SuccessorNode> successors;
430 if (lexer.is(Tokens.TokenKind.CARET)) {
431 successors = parseSuccessors();
432 } else {
433 successors = List.of();
434 }
435
436 // Attributes
437 final Map<String, Object> attributes;
438 if (lexer.is(Tokens.TokenKind.MONKEYS_AT)) {
439 attributes = parseAttributes();
440 } else {
441 attributes = Map.of();
442 }
443
444 // Bodies
445 List<BodyNode> bodies;
446 if (lexer.is(Tokens.TokenKind.CARET) || lexer.is(Tokens.TokenKind.LPAREN)) {
447 bodies = parseBodies();
448 } else {
449 bodies = List.of();
450 }
451
452 lexer.accept(Tokens.TokenKind.SEMI);
453
454 return new OpNode(operationResult, operationName, operands, successors, attributes, bodies);
455 }
456
457 Map<String, Object> parseAttributes() {
458 Map<String, Object> attributes = new HashMap<>();
459 while (lexer.acceptIf(Tokens.TokenKind.MONKEYS_AT)) {
460 String attributeName;
461 if (isNameStart()) {
462 attributeName = parseName();
463 lexer.accept(Tokens.TokenKind.EQ);
464 } else {
465 attributeName = "";
466 }
467 Object attributeValue = parseAttributeValue();
468 attributes.put(attributeName, attributeValue);
469 }
470 return attributes;
471 }
472
473 boolean isNameStart() {
474 // we need to lookahead to see if we can find an identifier followed by a '=',
475 // in which case we know what we're looking at is an attribute name
476 int curr = 0;
477 while (true) {
478 if (lexer.token(curr++).kind != TokenKind.IDENTIFIER) {
479 return false;
480 }
481 TokenKind next = lexer.token(curr++).kind;
482 if (next == TokenKind.EQ) {
483 return true;
484 } else if (next != TokenKind.DOT) {
485 return false;
486 }
487 }
488 }
489
490 Object parseAttributeValue() {
491 if (lexer.is(Tokens.TokenKind.IDENTIFIER)) {
492 return DescParser.parseExTypeElem(lexer);
493 }
494
495 Object value = parseLiteral(lexer.token());
496 lexer.nextToken();
497
498 return value;
499 }
500
501 Object parseLiteral(Tokens.Token t) {
502 return switch (t.kind) {
503 case STRINGLITERAL -> t.stringVal();
504 case NULL -> ExternalizedOp.NULL_ATTRIBUTE_VALUE;
505 case CHARLITERAL -> t.stringVal().charAt(0);
506 case TRUE -> true;
507 case FALSE -> false;
508 default -> parseNumericLiteral(t);
509 };
510 }
511
512 Object parseNumericLiteral(Tokens.Token t) {
513 String minusOpt = "";
514 if (t.kind == TokenKind.SUB) {
515 minusOpt = "-";
516 lexer.nextToken();
517 t = lexer.token();
518 }
519 return switch (t.kind) {
520 case INTLITERAL -> Integer.valueOf(minusOpt + t.stringVal());
521 case LONGLITERAL -> Long.valueOf(minusOpt + t.stringVal());
522 case FLOATLITERAL -> Float.valueOf(minusOpt + t.stringVal());
523 case DOUBLELITERAL -> Double.valueOf(minusOpt + t.stringVal());
524 default -> throw lexer.unexpected();
525 };
526 }
527
528 List<String> parseOperands() {
529 List<String> operands = new ArrayList<>();
530 while (lexer.is(Tokens.TokenKind.VALUE_IDENTIFIER)) {
531 operands.add(lexer.token().name().substring(1));
532 lexer.nextToken();
533 }
534 return operands;
535 }
536
537 List<SuccessorNode> parseSuccessors() {
538 List<SuccessorNode> successors = new ArrayList<>();
539
540 while (lexer.is(Tokens.TokenKind.CARET) && !isBody()) {
541 lexer.nextToken();
542 successors.add(parseSuccessor());
543 }
544
545 return successors;
546 }
547
548 // Lookahead from "^" to determine if Body
549 boolean isBody() {
550 assert lexer.is(Tokens.TokenKind.CARET);
551
552 int pos = 1;
553 lexer.token(pos++);
554 assert lexer.token(1).kind == Tokens.TokenKind.IDENTIFIER;
555
556 if (lexer.token(pos++).kind != Tokens.TokenKind.LPAREN) {
557 return false;
558 }
559
560 Tokens.Token t;
561 while ((t = lexer.token(pos++)).kind != Tokens.TokenKind.RPAREN) {
562 if (t.kind == Tokens.TokenKind.EOF) {
563 return false;
564 } else if (t.kind == Tokens.TokenKind.COLON) {
565 // Encountered Value
566 return true;
567 }
568 }
569
570 // Encountered return type
571 return lexer.token(pos++).kind == Tokens.TokenKind.IDENTIFIER;
572 }
573
574 SuccessorNode parseSuccessor() {
575 String blockName = lexer.accept(Tokens.TokenKind.IDENTIFIER).name();
576
577 List<String> arguments = new ArrayList<>();
578 if (lexer.acceptIf(Tokens.TokenKind.LPAREN) && !lexer.acceptIf(Tokens.TokenKind.RPAREN)) {
579 do {
580 arguments.add(lexer.accept(Tokens.TokenKind.VALUE_IDENTIFIER).name().substring(1));
581 } while (lexer.acceptIf(Tokens.TokenKind.COMMA));
582 lexer.accept(Tokens.TokenKind.RPAREN);
583 }
584
585 return new SuccessorNode(blockName, arguments);
586 }
587
588 List<BodyNode> parseBodies() {
589 List<BodyNode> bodies = new ArrayList<>();
590 while (lexer.is(Tokens.TokenKind.CARET) || lexer.is(Tokens.TokenKind.LPAREN)) {
591 BodyNode body = parseBody();
592 bodies.add(body);
593 }
594 return bodies;
595 }
596
597 BodyNode parseBody() {
598 // Body name
599 final String bodyName;
600 if (lexer.acceptIf(Tokens.TokenKind.CARET)) {
601 bodyName = lexer.accept(Tokens.TokenKind.IDENTIFIER).name();
602 } else {
603 bodyName = null;
604 }
605
606 // Entry block header
607 List<ValueNode> arguments = parseBlockHeaderArguments(true);
608 // Body return type
609 ExternalizedTypeElement rtype = parseExTypeElem();
610
611 lexer.accept(Tokens.TokenKind.ARROW);
612 lexer.accept(Tokens.TokenKind.LBRACE);
613
614 List<BlockNode> blocks = parseBlocks(bodyName, arguments);
615
616 lexer.accept(Tokens.TokenKind.RBRACE);
617
618 return new BodyNode(rtype, blocks);
619 }
620
621 List<ValueNode> parseBlockHeaderArguments(boolean isEntryBlock) {
622 boolean parseArguments;
623 if (isEntryBlock) {
624 lexer.accept(Tokens.TokenKind.LPAREN);
625 parseArguments = true;
626 } else {
627 parseArguments = lexer.acceptIf(Tokens.TokenKind.LPAREN);
628 }
629 if (!parseArguments || lexer.acceptIf(Tokens.TokenKind.RPAREN)) {
630 return new ArrayList<>();
631 }
632
633 List<ValueNode> arguments = new ArrayList<>();
634 do {
635 arguments.add(parseValueNode());
636 } while (lexer.acceptIf(Tokens.TokenKind.COMMA));
637 lexer.accept(Tokens.TokenKind.RPAREN);
638
639 return arguments;
640 }
641
642 ValueNode parseValueNode() {
643 String valueName = lexer.accept(Tokens.TokenKind.VALUE_IDENTIFIER).name().substring(1);
644
645 lexer.accept(Tokens.TokenKind.COLON);
646
647 ExternalizedTypeElement type = parseExTypeElem();
648
649 return new ValueNode(valueName, type);
650 }
651
652 List<BlockNode> parseBlocks(String entryBlockName, List<ValueNode> entryBlockArguments) {
653 List<BlockNode> blocks = new ArrayList<>();
654
655 // Entry block ops
656 BlockNode entryBlock = new BlockNode(entryBlockName, entryBlockArguments, parseOperations());
657 blocks.add(entryBlock);
658
659 // Subsequent blocks
660 while (lexer.acceptIf(Tokens.TokenKind.CARET)) {
661 String blockName = lexer.accept(Tokens.TokenKind.IDENTIFIER).name();
662 List<ValueNode> blockArguments = parseBlockHeaderArguments(false);
663
664 lexer.accept(Tokens.TokenKind.COLON);
665
666 BlockNode block = new BlockNode(blockName, blockArguments, parseOperations());
667 blocks.add(block);
668 }
669
670 return blocks;
671 }
672
673 List<OpNode> parseOperations() {
674 List<OpNode> ops = new ArrayList<>();
675 while (lexer.is(Tokens.TokenKind.MONKEYS_AT) || lexer.is(Tokens.TokenKind.VALUE_IDENTIFIER) || lexer.is(Tokens.TokenKind.IDENTIFIER)) {
676 OpNode op = parseOperation();
677 ops.add(op);
678 }
679 return ops;
680 }
681
682 String parseName() {
683 Tokens.Token t = lexer.accept(Tokens.TokenKind.IDENTIFIER);
684 StringBuilder name = new StringBuilder();
685 name.append(t.name());
686 while (lexer.acceptIf(Tokens.TokenKind.DOT)) {
687 name.append(Tokens.TokenKind.DOT.name);
688 t = lexer.accept(Tokens.TokenKind.IDENTIFIER);
689 name.append(t.name());
690 }
691 return name.toString();
692 }
693
694 ExternalizedTypeElement parseExTypeElem() {
695 return JavaTypeUtils.inflate(DescParser.parseExTypeElem(lexer));
696 }
697 }
698