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