Mercurial > hg > truffle

comparison graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeUtil.java @ 7267:a4b84ba6dc2e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Introduction of the Truffle API for efficient implementation of dynamic languages on top of the Graal VM. New projects com.oracle.truffle.api for the API definition and com.oracle.truffle.api.test for API tests and documentation.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Tue, 18 Dec 2012 15:33:55 +0100
parents
children 5e3d1a68664e
comparison
equal deleted inserted replaced
7259:494d99e07614 7267:a4b84ba6dc2e
1 /*
2 * Copyright (c) 2012, 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.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package com.oracle.truffle.api.nodes;
24
25 import java.io.*;
26 import java.lang.annotation.*;
27 import java.lang.reflect.*;
28 import java.util.*;
29
30 import sun.misc.*;
31
32 /**
33 * Utility class that manages the special access methods for node instances.
34 */
35 public class NodeUtil {
36
37 public static final class NodeClass {
38
39 private final Class parentClass;
40 private final long[] nodeFieldOffsets;
41 private final Class[] nodeFieldClasses;
42 private final long[] nodeArrayFieldOffsets;
43 private final Class[] nodeArrayFieldClasses;
44 private final long parentOffset;
45 private final long[] nodeDataFieldOffsets;
46 private final Class< ? >[] nodeDataFieldClasses;
47
48 private static final Map<Class< ? >, NodeClass> nodeClasses = new IdentityHashMap<>();
49
50 public static NodeClass get(Class< ? > clazz) {
51 NodeClass nodeClass = nodeClasses.get(clazz);
52 if (nodeClass == null) {
53 nodeClass = new NodeClass(clazz);
54 nodeClasses.put(clazz, nodeClass);
55 }
56 return nodeClass;
57 }
58
59 private NodeClass(Class< ? > clazz) {
60 // scan object fields
61 Class< ? > parentClassTmp = null;
62 List<Long> nodeFieldOffsetsList = new ArrayList<>();
63 List<Class< ? >> nodeFieldClassesList = new ArrayList<>();
64 List<Long> nodeArrayFieldOffsetsList = new ArrayList<>();
65 List<Class< ? >> nodeArrayFieldClassesList = new ArrayList<>();
66 List<Long> nodeDataFieldOffsetList = new ArrayList<>();
67 List<Class< ? >> nodeDataFieldClassList = new ArrayList<>();
68 Field[] fields = getAllFields(clazz);
69 long parentOffsetTemp = -1;
70 for (Field field : fields) {
71 if (Modifier.isStatic(field.getModifiers()) || field.isSynthetic()) {
72 continue;
73 }
74
75 // Node fields
76 if (Node.class.isAssignableFrom(field.getType())) {
77 if (!field.getName().equals("parent")) {
78 nodeFieldOffsetsList.add(unsafe.objectFieldOffset(field));
79 nodeFieldClassesList.add(field.getType());
80 } else {
81 parentOffsetTemp = unsafe.objectFieldOffset(field);
82 parentClassTmp = field.getType();
83 }
84 } else if (field.getType().getComponentType() != null && Node.class.isAssignableFrom(field.getType().getComponentType())) {
85 nodeArrayFieldOffsetsList.add(unsafe.objectFieldOffset(field));
86 nodeArrayFieldClassesList.add(field.getType());
87 } else {
88 nodeDataFieldOffsetList.add(unsafe.objectFieldOffset(field));
89 nodeDataFieldClassList.add(field.getType());
90 }
91 }
92 this.parentClass = parentClassTmp;
93 this.nodeFieldOffsets = toLongArray(nodeFieldOffsetsList);
94 this.nodeFieldClasses = nodeFieldClassesList.toArray(new Class[nodeFieldClassesList.size()]);
95 this.nodeArrayFieldOffsets = toLongArray(nodeArrayFieldOffsetsList);
96 this.nodeArrayFieldClasses = nodeArrayFieldClassesList.toArray(new Class[nodeArrayFieldClassesList.size()]);
97 this.nodeDataFieldOffsets = toLongArray(nodeDataFieldOffsetList);
98 this.nodeDataFieldClasses = nodeDataFieldClassList.toArray(new Class< ? >[nodeDataFieldClassList.size()]);
99
100 this.parentOffset = parentOffsetTemp;
101 }
102 }
103
104 public static class NodeIterator implements Iterator<Node> {
105
106 private final Node node;
107 private final NodeClass nodeClass;
108 private final int childrenCount;
109 private int index;
110
111 public NodeIterator(Node node) {
112 this(node, 0);
113 }
114
115 public NodeIterator(Node node, int index) {
116 this.node = node;
117 this.index = index;
118 this.nodeClass = NodeClass.get(node.getClass());
119 this.childrenCount = childrenCount();
120 }
121
122 private int childrenCount() {
123 int nodeCount = nodeClass.nodeFieldOffsets.length;
124 for (long fieldOffset : nodeClass.nodeArrayFieldOffsets) {
125 Node[] children = ((Node[]) unsafe.getObject(node, fieldOffset));
126 if (children != null) {
127 nodeCount += children.length;
128 }
129 }
130 return nodeCount;
131 }
132
133 private Node nodeAt(int idx) {
134 int nodeCount = nodeClass.nodeFieldOffsets.length;
135 if (idx < nodeCount) {
136 return (Node) unsafe.getObject(node, nodeClass.nodeFieldOffsets[idx]);
137 } else {
138 for (long fieldOffset : nodeClass.nodeArrayFieldOffsets) {
139 Node[] nodeArray = (Node[]) unsafe.getObject(node, fieldOffset);
140 if (idx < nodeCount + nodeArray.length) {
141 return nodeArray[idx - nodeCount];
142 }
143 nodeCount += nodeArray.length;
144 }
145 }
146 return null;
147 }
148
149 private void forward() {
150 if (index < childrenCount) {
151 index++;
152 }
153 }
154
155 @Override
156 public boolean hasNext() {
157 return index < childrenCount;
158 }
159
160 @Override
161 public Node next() {
162 try {
163 return nodeAt(index);
164 } finally {
165 forward();
166 }
167 }
168
169 @Override
170 public void remove() {
171 throw new UnsupportedOperationException();
172 }
173 }
174
175 private static long[] toLongArray(List<Long> list) {
176 long[] array = new long[list.size()];
177 for (int i = 0; i < list.size(); i++) {
178 array[i] = list.get(i);
179 }
180 return array;
181 }
182
183 private static final Unsafe unsafe = getUnsafe();
184
185 private static Unsafe getUnsafe() {
186 try {
187 return Unsafe.getUnsafe();
188 } catch (SecurityException e) {
189 }
190 try {
191 Field theUnsafeInstance = Unsafe.class.getDeclaredField("theUnsafe");
192 theUnsafeInstance.setAccessible(true);
193 return (Unsafe) theUnsafeInstance.get(Unsafe.class);
194 } catch (Exception e) {
195 throw new RuntimeException("exception while trying to get Unsafe.theUnsafe via reflection:", e);
196 }
197 }
198
199 @SuppressWarnings("unchecked")
200 public static <T extends Node> T cloneNode(T orig) {
201 Class< ? extends Node> clazz = orig.getClass();
202 NodeClass nodeClass = NodeClass.get(clazz);
203 Node clone = orig.copy();
204 if (clone == null) {
205 return null;
206 }
207
208 unsafe.putObject(clone, nodeClass.parentOffset, null);
209
210 for (long fieldOffset : nodeClass.nodeFieldOffsets) {
211 Node child = (Node) unsafe.getObject(orig, fieldOffset);
212 if (child != null) {
213 Node clonedChild = cloneNode(child);
214 if (clonedChild == null) {
215 return null;
216 }
217
218 unsafe.putObject(clonedChild, nodeClass.parentOffset, clone);
219 unsafe.putObject(clone, fieldOffset, clonedChild);
220 }
221 }
222 for (long fieldOffset : nodeClass.nodeArrayFieldOffsets) {
223 Node[] children = (Node[]) unsafe.getObject(orig, fieldOffset);
224 if (children != null) {
225 Node[] clonedChildren = new Node[children.length];
226 for (int i = 0; i < children.length; i++) {
227 Node clonedChild = cloneNode(children[i]);
228 if (clonedChild == null) {
229 return null;
230 }
231
232 clonedChildren[i] = clonedChild;
233 unsafe.putObject(clonedChild, nodeClass.parentOffset, clone);
234 }
235 unsafe.putObject(clone, fieldOffset, clonedChildren);
236 }
237 }
238 return (T) clone;
239 }
240
241 public static List<Object> findNodeChildren(Object node) {
242 List<Object> nodes = new ArrayList<>();
243 NodeClass nodeClass = NodeClass.get(node.getClass());
244
245 for (long fieldOffset : nodeClass.nodeFieldOffsets) {
246 Object child = unsafe.getObject(node, fieldOffset);
247 if (child != null) {
248 nodes.add(child);
249 }
250 }
251 for (long fieldOffset : nodeClass.nodeArrayFieldOffsets) {
252 Object[] children = (Object[]) unsafe.getObject(node, fieldOffset);
253 if (children != null) {
254 nodes.addAll(Arrays.asList(children));
255 }
256 }
257
258 return nodes;
259 }
260
261 public static void replaceChild(Node parent, Node oldChild, Node newChild) {
262 NodeClass nodeClass = NodeClass.get(parent.getClass());
263
264 for (long fieldOffset : nodeClass.nodeFieldOffsets) {
265 if (unsafe.getObject(parent, fieldOffset) == oldChild) {
266 unsafe.putObject(parent, fieldOffset, newChild);
267 }
268 }
269 for (long fieldOffset : nodeClass.nodeArrayFieldOffsets) {
270 Node[] array = (Node[]) unsafe.getObject(parent, fieldOffset);
271 if (array != null) {
272 for (int i = 0; i < array.length; i++) {
273 if (array[i] == oldChild) {
274 array[i] = newChild;
275 return;
276 }
277 }
278 }
279 }
280 }
281
282 public static long[] getNodeDataFieldOffsets(Class< ? > nodeClass) {
283 NodeClass clazz = NodeClass.get(nodeClass);
284 return Arrays.copyOf(clazz.nodeDataFieldOffsets, clazz.nodeDataFieldClasses.length);
285 }
286
287 public static Class[] getNodeDataFieldClasses(Class< ? > nodeClass) {
288 NodeClass clazz = NodeClass.get(nodeClass);
289 return Arrays.copyOf(clazz.nodeDataFieldClasses, clazz.nodeDataFieldClasses.length);
290 }
291
292 public static long getNodeParentOffset(Class< ? > nodeClass) {
293 NodeClass clazz = NodeClass.get(nodeClass);
294 return clazz.parentOffset;
295 }
296
297 /** Returns the number of Node field declarations in the class hierarchy. */
298 public static long[] getNodeFieldOffsets(Class< ? > nodeClass) {
299 NodeClass clazz = NodeClass.get(nodeClass);
300 return Arrays.copyOf(clazz.nodeFieldOffsets, clazz.nodeFieldOffsets.length);
301 }
302
303 /** Returns the number of Node[] declaration in the class hierarchy. */
304 public static long[] getNodeFieldArrayOffsets(Class< ? > nodeClass) {
305 NodeClass clazz = NodeClass.get(nodeClass);
306 return Arrays.copyOf(clazz.nodeArrayFieldOffsets, clazz.nodeArrayFieldOffsets.length);
307 }
308
309 public static Class[] getNodeFieldArrayClasses(Class< ? > nodeClass) {
310 NodeClass clazz = NodeClass.get(nodeClass);
311 return Arrays.copyOf(clazz.nodeArrayFieldClasses, clazz.nodeArrayFieldClasses.length);
312 }
313
314 public static Class getNodeParentClass(Class< ? > nodeClass) {
315 return NodeClass.get(nodeClass).parentClass;
316 }
317
318 public static Class[] getNodeFieldClasses(Class< ? > nodeClass) {
319 NodeClass clazz = NodeClass.get(nodeClass);
320 return Arrays.copyOf(clazz.nodeFieldClasses, clazz.nodeFieldClasses.length);
321 }
322
323 /** Returns all declared fields in the class hierarchy. */
324 public static Field[] getAllFields(Class< ? extends Object> clazz) {
325 Field[] declaredFields = clazz.getDeclaredFields();
326 if (clazz.getSuperclass() != null) {
327 return concat(getAllFields(clazz.getSuperclass()), declaredFields);
328 }
329 return declaredFields;
330 }
331
332 public static <T> T[] concat(T[] first, T[] second) {
333 T[] result = Arrays.copyOf(first, first.length + second.length);
334 System.arraycopy(second, 0, result, first.length, second.length);
335 return result;
336 }
337
338 /** find annotation in class/interface hierarchy. */
339 public static <T extends Annotation> T findAnnotation(Class< ? > clazz, Class<T> annotationClass) {
340 if (clazz.getAnnotation(annotationClass) != null) {
341 return clazz.getAnnotation(annotationClass);
342 } else {
343 for (Class< ? > intf : clazz.getInterfaces()) {
344 if (intf.getAnnotation(annotationClass) != null) {
345 return intf.getAnnotation(annotationClass);
346 }
347 }
348 if (clazz.getSuperclass() != null) {
349 return findAnnotation(clazz.getSuperclass(), annotationClass);
350 }
351 }
352 return null;
353 }
354
355 @SuppressWarnings("unchecked")
356 public static <T extends Node> T findParent(final Node start, final Class<T> clazz) {
357 assert start != null;
358 if (clazz.isInstance(start.getParent())) {
359 return (T) start.getParent();
360 } else {
361 return start.getParent() != null ? findParent(start.getParent(), clazz) : null;
362 }
363 }
364
365 @SuppressWarnings("unchecked")
366 public static <I> I findParentInterface(final Node start, final Class<I> clazz) {
367 assert start != null;
368 if (clazz.isInstance(start.getParent())) {
369 return (I) start.getParent();
370 } else {
371 return (start.getParent() != null ? findParentInterface(start.getParent(), clazz) : null);
372 }
373 }
374
375 @SuppressWarnings("unchecked")
376 public static <T> T findFirstNodeInstance(Object root, Class<T> clazz) {
377 List<Object> childNodes = findNodeChildren(root);
378
379 for (Object childNode : childNodes) {
380 if (clazz.isInstance(childNode)) {
381 return (T) childNode;
382 } else {
383 return findFirstNodeInstance(childNode, clazz);
384 }
385 }
386 return null;
387 }
388
389 public static <T extends Node> List<T> findAllNodeInstances(final Node root, final Class<T> clazz) {
390 final List<T> nodeList = new ArrayList<>();
391 root.accept(new NodeVisitor() {
392
393 @SuppressWarnings("unchecked")
394 @Override
395 public boolean visit(Node node) {
396 if (clazz.isInstance(node)) {
397 nodeList.add((T) node);
398 }
399 return true;
400 }
401 });
402 return nodeList;
403 }
404
405 // Don't visit found node instances.
406 public static <T extends Node> List<T> findNodeInstancesShallow(final Node root, final Class<T> clazz) {
407 final List<T> nodeList = new ArrayList<>();
408 root.accept(new NodeVisitor() {
409
410 @SuppressWarnings("unchecked")
411 @Override
412 public boolean visit(Node node) {
413 if (clazz.isInstance(node)) {
414 nodeList.add((T) node);
415 return false;
416 }
417 return true;
418 }
419 });
420 return nodeList;
421 }
422
423 /** Find node instances within current function only (not in nested functions). */
424 public static <T extends Node> List<T> findNodeInstancesInFunction(final Node root, final Class<T> clazz) {
425 final List<T> nodeList = new ArrayList<>();
426 root.accept(new NodeVisitor() {
427
428 @SuppressWarnings("unchecked")
429 @Override
430 public boolean visit(Node node) {
431 if (clazz.isInstance(node)) {
432 nodeList.add((T) node);
433 } else if (node instanceof RootNode && node != root) {
434 return false;
435 }
436 return true;
437 }
438 });
439 return nodeList;
440 }
441
442 public static <I> List<I> findNodeInstancesInFunctionInterface(final Node root, final Class<I> clazz) {
443 final List<I> nodeList = new ArrayList<>();
444 root.accept(new NodeVisitor() {
445
446 @SuppressWarnings("unchecked")
447 @Override
448 public boolean visit(Node node) {
449 if (clazz.isInstance(node)) {
450 nodeList.add((I) node);
451 } else if (node instanceof RootNode && node != root) {
452 return false;
453 }
454 return true;
455 }
456 });
457 return nodeList;
458 }
459
460 public static String printTreeToString(Node node) {
461 ByteArrayOutputStream byteOut = new ByteArrayOutputStream();
462 printTree(new PrintStream(byteOut), node);
463 try {
464 byteOut.flush();
465 } catch (IOException e) {
466 }
467 return new String(byteOut.toByteArray());
468 }
469
470 /**
471 * Prints a human readable form of a {@link Node} AST to the given {@link PrintStream}. This print method does not
472 * check for cycles in the node structure.
473 *
474 * @param p the {@link PrintStream} to print to.
475 * @param node the root node to write
476 */
477 public static void printTree(PrintStream p, Node node) {
478 printTree(p, node, new NodeTreeResolver());
479 }
480
481 /**
482 * Prints a human readable form of a tree to the given {@link PrintStream}. The {@link TreeResolver} interface needs
483 * to be implemented to specify how the method can read the tree from plain a object.
484 *
485 * @param p the {@link PrintStream} to print to.
486 * @param o the root object to be printed.
487 * @param resolver an implementation of a tree resolver
488 */
489 public static void printTree(PrintStream p, Object o, TreeResolver resolver) {
490 printTree(p, o, resolver, 1);
491 p.println();
492 }
493
494 private static void printTree(PrintStream p, Object node, TreeResolver resolver, int level) {
495 if (node == null) {
496 p.print("null");
497 return;
498 }
499
500 p.print(node.getClass().getSimpleName());
501
502 Field[] fields = NodeUtil.getAllFields(node.getClass());
503 p.print("(");
504
505 ArrayList<Field> childFields = new ArrayList<>();
506
507 boolean first = true;
508 for (int i = 0; i < fields.length; i++) {
509 Field field = fields[i];
510 if (Modifier.isStatic(field.getModifiers()) || resolver.isFiltered(field)) {
511 continue;
512 }
513 if (resolver.isChildObject(field) || resolver.isChildArrayObject(field)) {
514 childFields.add(field);
515 }
516 if (!resolver.isDataField(field)) {
517 continue;
518 }
519 if (!first) {
520 p.print(", ");
521 } else {
522 first = false;
523 }
524
525 Object value = getObjectValue(node, field.getType(), unsafe.objectFieldOffset(field));
526
527 p.print(field.getName());
528 p.print(" = ");
529 p.print(resolver.toString(value));
530 }
531 p.print(")");
532
533 if (childFields.size() != 0) {
534 p.print(" {");
535 }
536
537 // I refetch the fields to get declaration order.
538 for (int i = 0; i < childFields.size(); i++) {
539 Field field = childFields.get(i);
540 Class< ? > fieldClass = field.getType();
541 String name = field.getName();
542
543 long offset = unsafe.objectFieldOffset(field);
544
545 Object value = getObjectValue(node, fieldClass, offset);
546
547 printNewLine(p, level);
548 p.print(name);
549 if (value == null) {
550 p.print(" = null ");
551 } else if (resolver.isChildObject(field)) {
552 p.print(" = ");
553 printTree(p, value, resolver, level + 1);
554 } else if (resolver.isChildArrayObject(field)) {
555 Object[] objectArray = resolver.convertToArray(field, value);
556 if (objectArray.length == 0) {
557 p.print(" = []");
558 } else {
559 p.print(" = [");
560 for (int j = 0; j < objectArray.length; j++) {
561 printTree(p, objectArray[j], resolver, level + 1);
562 if (j < objectArray.length - 1) {
563 p.print(", ");
564 }
565 }
566 p.print("]");
567 }
568 } else {
569 assert false;
570 }
571 }
572
573 if (childFields.size() != 0) {
574 printNewLine(p, level - 1);
575 p.print("}");
576 }
577 }
578
579 private static Object getObjectValue(Object base, Class< ? > fieldClass, long offset) {
580 if (fieldClass == boolean.class) {
581 return unsafe.getBoolean(base, offset);
582 } else if (fieldClass == byte.class) {
583 return unsafe.getByte(base, offset);
584 } else if (fieldClass == short.class) {
585 return unsafe.getShort(base, offset);
586 } else if (fieldClass == char.class) {
587 return unsafe.getChar(base, offset);
588 } else if (fieldClass == int.class) {
589 return unsafe.getInt(base, offset);
590 } else if (fieldClass == long.class) {
591 return unsafe.getLong(base, offset);
592 } else if (fieldClass == float.class) {
593 return unsafe.getFloat(base, offset);
594 } else if (fieldClass == double.class) {
595 return unsafe.getDouble(base, offset);
596 } else {
597 return unsafe.getObject(base, offset);
598 }
599 }
600
601 private static void printNewLine(PrintStream p, int level) {
602 p.println();
603 for (int i = 0; i < level; i++) {
604 p.print(" ");
605 }
606 }
607
608 private static class NodeTreeResolver implements TreeResolver {
609
610 @Override
611 public boolean isFiltered(Field f) {
612 if (f.getName().equals("parent")) {
613 return true;
614 }
615 return f.isSynthetic();
616 }
617
618 @Override
619 public boolean isDataField(Field f) {
620 return !isChildArrayObject(f) && !isChildObject(f);
621 }
622
623 @Override
624 public boolean isChildObject(Field f) {
625 return Node.class.isAssignableFrom(f.getType());
626 }
627
628 @Override
629 public boolean isChildArrayObject(Field f) {
630 return f.getType().getComponentType() != null && Node.class.isAssignableFrom(f.getType().getComponentType());
631 }
632
633 @Override
634 public Object[] convertToArray(Field f, Object data) {
635 return (Object[]) data;
636 }
637
638 @Override
639 public String toString(Object o) {
640 return o == null ? "null" : o.toString();
641 }
642 }
643
644 /**
645 * Specifies how a tree can be built from plain objects.
646 */
647 public interface TreeResolver {
648
649 /**
650 * Returns true if a {@link Field} is filtered from the tree.
651 *
652 * @param f the field to check
653 */
654 boolean isFiltered(Field f);
655
656 /**
657 * Returns true if a {@link Field} is a field that contains a data value which should not be traversed
658 * recursively.
659 *
660 * @param f the field to check
661 * @return true if a the given field is a data field else false.
662 */
663 boolean isDataField(Field f);
664
665 /**
666 * Returns true if a {@link Field} is a field that contains an {@link Object} which should be recursively
667 * visited.
668 *
669 * @param f the field to check
670 * @return true if a the given field is a child field else false.
671 */
672 boolean isChildObject(Field f);
673
674 /**
675 * Returns true if a {@link Field} is a field that contains any kind of list/array structure which itself holds
676 * values that should be recursively visited.
677 *
678 * @param f the field to check
679 * @return true if a the given field is a child array/list field else false.
680 */
681 boolean isChildArrayObject(Field f);
682
683 /**
684 * Converts an given child array object to array which can be traversed. This is especially useful to convert
685 * any kind of list structure to a traversable array.
686 *
687 * @param f the field for meta data needed to convert the data {@link Object}.
688 * @param value the actual value of the child array/list object.
689 * @return the converted {@link Object} array.
690 */
691 Object[] convertToArray(Field f, Object value);
692
693 /**
694 * Returns a human readable string for any data field object in the tree.
695 *
696 * @param o the object to convert to string.
697 * @return the converted string
698 */
699 String toString(Object o);
700 }
701
702 }