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