Revert "Revert "Import external/python/jinja into master""

This reverts commit 81aec74062b5c629b3408f7f3d18343ec0bbcab8.

Reason for revert: It seems Jinja folder is empty. Revert the revert to add files back.

Third-party review: ag/11821018
Change-Id: I4429a3b3448cdf2eb62ec388392a2a29fa3dbc21

1 files changed, 79 insertions, 0 deletions

diff --git a/src/jinja2/visitor.py b/src/jinja2/visitor.py
new file mode 100644
index 00000000..590fa9eb
--- /dev/null
+++ b/src/jinja2/visitor.py
@@ -0,0 +1,79 @@
+"""API for traversing the AST nodes. Implemented by the compiler and
+meta introspection.
+"""
+from .nodes import Node
+
+
+class NodeVisitor:
+    """Walks the abstract syntax tree and call visitor functions for every
+    node found.  The visitor functions may return values which will be
+    forwarded by the `visit` method.
+
+    Per default the visitor functions for the nodes are ``'visit_'`` +
+    class name of the node.  So a `TryFinally` node visit function would
+    be `visit_TryFinally`.  This behavior can be changed by overriding
+    the `get_visitor` function.  If no visitor function exists for a node
+    (return value `None`) the `generic_visit` visitor is used instead.
+    """
+
+    def get_visitor(self, node):
+        """Return the visitor function for this node or `None` if no visitor
+        exists for this node.  In that case the generic visit function is
+        used instead.
+        """
+        return getattr(self, f"visit_{node.__class__.__name__}", None)
+
+    def visit(self, node, *args, **kwargs):
+        """Visit a node."""
+        f = self.get_visitor(node)
+        if f is not None:
+            return f(node, *args, **kwargs)
+        return self.generic_visit(node, *args, **kwargs)
+
+    def generic_visit(self, node, *args, **kwargs):
+        """Called if no explicit visitor function exists for a node."""
+        for node in node.iter_child_nodes():
+            self.visit(node, *args, **kwargs)
+
+
+class NodeTransformer(NodeVisitor):
+    """Walks the abstract syntax tree and allows modifications of nodes.
+
+    The `NodeTransformer` will walk the AST and use the return value of the
+    visitor functions to replace or remove the old node.  If the return
+    value of the visitor function is `None` the node will be removed
+    from the previous location otherwise it's replaced with the return
+    value.  The return value may be the original node in which case no
+    replacement takes place.
+    """
+
+    def generic_visit(self, node, *args, **kwargs):
+        for field, old_value in node.iter_fields():
+            if isinstance(old_value, list):
+                new_values = []
+                for value in old_value:
+                    if isinstance(value, Node):
+                        value = self.visit(value, *args, **kwargs)
+                        if value is None:
+                            continue
+                        elif not isinstance(value, Node):
+                            new_values.extend(value)
+                            continue
+                    new_values.append(value)
+                old_value[:] = new_values
+            elif isinstance(old_value, Node):
+                new_node = self.visit(old_value, *args, **kwargs)
+                if new_node is None:
+                    delattr(node, field)
+                else:
+                    setattr(node, field, new_node)
+        return node
+
+    def visit_list(self, node, *args, **kwargs):
+        """As transformers may return lists in some places this method
+        can be used to enforce a list as return value.
+        """
+        rv = self.visit(node, *args, **kwargs)
+        if not isinstance(rv, list):
+            rv = [rv]
+        return rv