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