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