Summary: The Visitor pattern is not as well known among design patterns as the singleton pattern, but it is one of the few design patterns that everyone has a name for. However, due to the complexity of the visitor pattern, it is rarely used in applications. Through this article’s exploration, we are sure to develop new insights and find more flexible and widespread ways to use it.
The author | | hanging scale source ali technology to the public
The Visitor pattern is not as well known among design patterns as the singleton pattern, but it is one of the few design patterns that everyone has a name for (the others are probably the “observer pattern” and “factory pattern”). However, due to the complexity of the visitor pattern, it is rarely used in applications. Through this article’s exploration, we are sure to develop new insights and find more flexible and widespread ways to use it.
Unlike most articles on design patterns, this article does not stick to rigid code templates. Instead, it starts directly from the practice of open source projects and application systems, compares other similar design patterns, and finally explains their nature in programming paradigms.
The visitor pattern in Calcite
It’s a good first step to get a sense of the complexity inherent in open source libraries, which often make use of visitor-style apis.
Calcite is a database base class library written in the Java language and used by well-known open source projects such as Hive and Spark. The SQL parsing module provides the API of the visitor mode. We can use its API to quickly obtain the information we need in SQL, taking all functions used in SQL as an example:
import org.apache.calcite.sql.SqlCall; import org.apache.calcite.sql.SqlFunction; import org.apache.calcite.sql.SqlNode; import org.apache.calcite.sql.parser.SqlParseException; import org.apache.calcite.sql.parser.SqlParser; import org.apache.calcite.sql.util.SqlBasicVisitor; import java.util.ArrayList; import java.util.List; public class CalciteTest { public static void main(String[] args) throws SqlParseException { String sql = "select concat('test-', upper(name)) from test limit 3"; SqlParser parser = SqlParser.create(sql); SqlNode stmt = parser.parseStmt(); FunctionExtractor functionExtractor = new FunctionExtractor(); stmt.accept(functionExtractor); // [CONCAT, UPPER] System.out.println(functionExtractor.getFunctions()); } private static class FunctionExtractor extends SqlBasicVisitor< Void> { private final List< String> functions = new ArrayList<>(); @Override public Void visit(SqlCall call) { if (call.getOperator() instanceof SqlFunction) { functions.add(call.getOperator().getName()); } return super.visit(call); } public List< String> getFunctions() { return functions; }}}Copy the codeThe FunctionExtractor is a subclass of SqlBasicVisitor and overrides its visit(SqlCall) method to get the function name and collect it in functions.
In addition to visit(SqlCall), you can also use visit(SqlLiteral) (constants), visit(SqlIdentifier) (table/column names), and so on to achieve more complex analysis.
One wonders, why doesn’t SqlParser just provide methods like getFunctions to get all the functions in SQL directly? In the example above, getFunctions may indeed be more convenient, but SQL is a complex structure and getFunctions is less flexible and performs worse for more complex analysis scenarios. If needed, it is quite simple to implement a FunctionExtractor like the one above to meet the requirements.
Two hands-on implementation of the visitor pattern
We tried to implement a simplified version of SqlVisitor.
Start by defining a simplified version of the SQL structure.
Select upper(name) from test where age > 20; Deconstructing to the hierarchy of this structure is shown as follows:
We construct the above structure directly in Java code:
SqlNode sql = new SelectNode(
new FieldsNode(Arrays.asList(
new FunctionCallExpression("upper", Arrays.asList(
new IdExpression("name")
))
)),
Arrays.asList("test"),
new WhereNode(Arrays.asList(new OperatorExpression(
new IdExpression("age"),
">",
new LiteralExpression("20")
)))
);
Copy the codeThe same method in this class is accept:
@Override
public < R> R accept(SqlVisitor< R> sqlVisitor) {
return sqlVisitor.visit(this);
}
Copy the codeThis is distributed to the SqlVisitor’s different visit methods via multistate:
abstract class SqlVisitor< R> {
abstract R visit(SelectNode selectNode);
abstract R visit(FieldsNode fieldsNode);
abstract R visit(WhereNode whereNode);
abstract R visit(IdExpression idExpression);
abstract R visit(FunctionCallExpression functionCallExpression);
abstract R visit(OperatorExpression operatorExpression);
abstract R visit(LiteralExpression literalExpression);
}
Copy the codeSQL structure-related classes are as follows:
Public abstract < R> R accept(SqlVisitor< R> SqlVisitor); } class SelectNode extends SqlNode { private final FieldsNode fields; private final List< String> from; private final WhereNode where; SelectNode(FieldsNode fields, List< String> from, WhereNode where) { this.fields = fields; this.from = from; this.where = where; } @Override public < R> R accept(SqlVisitor< R> sqlVisitor) { return sqlVisitor.visit(this); } / /... Get method omit} class FieldsNode extends SqlNode {private final List< Expression> fields; FieldsNode(List<Expression> fields) { this.fields = fields; } @Override public < R> R accept(SqlVisitor< R> sqlVisitor) { return sqlVisitor.visit(this); } } class WhereNode extends SqlNode { private final List< Expression> conditions; WhereNode(List< Expression> conditions) { this.conditions = conditions; } @Override public < R> R accept(SqlVisitor< R> sqlVisitor) { return sqlVisitor.visit(this); } } abstract class Expression extends SqlNode { } class IdExpression extends Expression { private final String id; protected IdExpression(String id) { this.id = id; } @Override public < R> R accept(SqlVisitor< R> sqlVisitor) { return sqlVisitor.visit(this); } } class FunctionCallExpression extends Expression { private final String name; private final List< Expression> arguments; FunctionCallExpression(String name, List< Expression> arguments) { this.name = name; this.arguments = arguments; } @Override public < R> R accept(SqlVisitor< R> sqlVisitor) { return sqlVisitor.visit(this); } } class LiteralExpression extends Expression { private final String literal; LiteralExpression(String literal) { this.literal = literal; } @Override public < R> R accept(SqlVisitor< R> sqlVisitor) { return sqlVisitor.visit(this); } } class OperatorExpression extends Expression { private final Expression left; private final String operator; private final Expression right; OperatorExpression(Expression left, String operator, Expression right) { this.left = left; this.operator = operator; this.right = right; } @Override public < R> R accept(SqlVisitor< R> sqlVisitor) { return sqlVisitor.visit(this); }}Copy the codeSome readers may have noticed that the code for each class’s Accept method is the same, so why not just write it in the parent class SqlNode? If we tried, we would find that the program failed because our SqlVisitor did not provide visit(SqlNode) at all. Even if visit(SqlNode) was added and the program was compiled, the results were not as expected. Because all calls to visit now point to visit(SqlNode), the other overloaded methods are meaningless.
The reason for this is that different visit methods have only different parameters from each other, which is called “overloading”. Java “overloading”, also known as “compile-time polymorphism”, only determines which method to call based on the type of this in visit(this) at compile time. Its type at compile time is SqlNode, although it may be a different subclass at run time.
So, we’ve often heard that it’s easier to write visitor patterns in dynamic languages, especially functional programming languages that support pattern matching (which is already well supported in Java 18). Let’s go back and re-implement this section using pattern matching to see if it’s much easier.
Next, as before, we use the SqlVisitor to try to parse out all the function calls in the SQL.
Implement a SqlVisitor that calls Accept based on the structure of the current node and finally assembles the results, adding function names to the collection when FunctionCallExpression is encountered:
class FunctionExtractor extends SqlVisitor< List< String>> { @Override List< String> visit(SelectNode selectNode) { List<String> res = new ArrayList<>(); res.addAll(selectNode.getFields().accept(this)); res.addAll(selectNode.getWhere().accept(this)); return res; } @Override List< String> visit(FieldsNode fieldsNode) { List< String> res = new ArrayList<>(); for (Expression field : fieldsNode.getFields()) { res.addAll(field.accept(this)); } return res; } @Override List< String> visit(WhereNode whereNode) { List< String> res = new ArrayList<>(); for (Expression condition : whereNode.getConditions()) { res.addAll(condition.accept(this)); } return res; } @Override List< String> visit(IdExpression idExpression) { return Collections.emptyList(); } @override List< String> visit(FunctionCallExpression FunctionCallExpression) {// Get the function name List< String> res = new ArrayList<>(); res.add(functionCallExpression.getName()); for (Expression argument : functionCallExpression.getArguments()) { res.addAll(argument.accept(this)); } return res; } @Override List< String> visit(OperatorExpression operatorExpression) { List< String> res = new ArrayList<>(); res.addAll(operatorExpression.getLeft().accept(this)); res.addAll(operatorExpression.getRight().accept(this)); return res; } @Override List< String> visit(LiteralExpression literalExpression) { return Collections.emptyList(); }}Copy the codeThe code in main looks like this:
Public static void main(String[] args) {SqlNode SQL = new SelectNode(//select // concat("test-", upper(name)) new FieldsNode(Arrays.asList( new FunctionCallExpression("concat", Arrays.asList( new LiteralExpression("test-"), new FunctionCallExpression( "upper", Arrays.asList(new IdExpression("name")) ) )) )), // from test Arrays.asList("test"), // where age > 20 new WhereNode(Arrays.asList(new OperatorExpression( new IdExpression("age"), ">", new LiteralExpression("20") ))) ); // Use FunctionExtractor FunctionExtractor FunctionExtractor = new FunctionExtractor(); List< String> functions = sql.accept(functionExtractor); // [concat, upper] System.out.println(functions); }Copy the codeThis is the implementation of the standard visitor pattern, which is intuitively more difficult to use than Calcite’s SqlBasicVisitor, so let’s implement the SqlBasicVisitor.
Visitor pattern and observer pattern
In FunctionExtractor implemented with Calcite, every time Calcite parses into a function, our implementation visit(SqlCall) is called, and it seems more appropriate to call it LISTEN (SqlCall) than visit. This also shows how closely the visitor pattern relates to the observer pattern.
In our own FunctionExtractor, most of the code iterates through various structures in some order, because the visitor pattern gives the user enough flexibility to let the implementer decide the order of iterating, or pry away the parts that don’t need iterating.
But our requirement to “parse out all the functions in SQL” doesn’t care about the order of traversal, as long as we are notified when “functions” pass through. For this simple requirement, the visitor pattern is a bit over-engineered, and the observer pattern is more appropriate.
Most open source projects that use the visitor pattern provide a default implementation for “standard visitors,” such as Calcite’s SqlBasicVisitor, which iterates through SQL structures in the default order, and the implementer simply overrides the parts it cares about, In this way, the observer mode is realized on the basis of the visitor mode, that is, the flexibility of the visitor mode is not lost, but the convenience of the observer mode is obtained.
Let’s add a SqlBasicVisitor to our implementation as well:
class SqlBasicVisitor< R> extends SqlVisitor< R> { @Override R visit(SelectNode selectNode) { selectNode.getFields().accept(this); selectNode.getWhere().accept(this); return null; } @Override R visit(FieldsNode fieldsNode) { for (Expression field : fieldsNode.getFields()) { field.accept(this); } return null; } @Override R visit(WhereNode whereNode) { for (Expression condition : whereNode.getConditions()) { condition.accept(this); } return null; } @Override R visit(IdExpression idExpression) { return null; } @Override R visit(FunctionCallExpression functionCallExpression) { for (Expression argument : functionCallExpression.getArguments()) { argument.accept(this); } return null; } @Override R visit(OperatorExpression operatorExpression) { operatorExpression.getLeft().accept(this); operatorExpression.getRight().accept(this); return null; } @Override R visit(LiteralExpression literalExpression) { return null; }}Copy the codeSqlBasicVisitor provides a default access order for each structure and uses this class to implement FunctionExtractor version 2:
class FunctionExtractor2 extends SqlBasicVisitor< Void> { private final List< String> functions = new ArrayList<>(); @Override Void visit(FunctionCallExpression functionCallExpression) { functions.add(functionCallExpression.getName()); return super.visit(functionCallExpression); } public List< String> getFunctions() { return functions; }}Copy the codeIts use is as follows:
class Main { public static void main(String[] args) { SqlNode sql = new SelectNode( new FieldsNode(Arrays.asList( new FunctionCallExpression("concat", Arrays.asList( new LiteralExpression("test-"), new FunctionCallExpression( "upper", Arrays.asList(new IdExpression("name")) ) )) )), Arrays.asList("test"), new WhereNode(Arrays.asList(new OperatorExpression( new IdExpression("age"), ">", new LiteralExpression("20") ))) ); FunctionExtractor2 functionExtractor = new FunctionExtractor2(); sql.accept(functionExtractor); System.out.println(functionExtractor.getFunctions()); }}Copy the codeVisitor model and responsibility chain model
ASM is also a library that provides the visitor pattern API for parsing and generating Java class files. It is used in every well-known Java open source project imaginable, and even implemented the Lambda expression feature of Java8 through it. ASM might not have been as popular if it had simply parsed and generated Java class files. More important, it abstracted common functions into small visitor utility classes, making complex bytecode operations as simple as building blocks.
Suppose you need to modify the class file as follows:
- Delete the name attribute
- Add the @nonNULL annotation to all attributes
But for reuse and modularity purposes, we wanted to separate the two steps into separate functional modules rather than write code together. In ASM, we can implement two small visitors separately, and then string them together to create a visitor that can fulfill our requirements.
Delete visitors from the name attribute:
Class DeleteFieldVisitor extends ClassVisitor {private final String deleteFieldName; private final String deleteFieldName; public DeleteFieldVisitor(ClassVisitor classVisitor, String deleteFieldName) { super(Opcodes.ASM9, classVisitor); this.deleteFieldName = deleteFieldName; } @Override public FieldVisitor visitField(int access, String name, String descriptor, String signature, Object value) {if (name.equals(deleteFieldName)) {return null; } // Super. visitField returns super.visitField(Access, name, descriptor, signature, descriptor) value); }}Copy the codeVisitors who annotate all attributes with @nonNULL:
class AddAnnotationVisitor extends ClassVisitor { public AddAnnotationVisitor(ClassVisitor classVisitor) { super(Opcodes.ASM9, classVisitor); } @Override public FieldVisitor visitField(int access, String name, String descriptor, String signature, Object value) { FieldVisitor fieldVisitor = super.visitField(access, name, descriptor, signature, value); / / downstream Visitor pass a @ NonNull additional annotations fieldVisitor. VisitAnnotation (" javax.mail/annotation/NonNull ", false); return fieldVisitor; }}Copy the codeIn main we string them together:
public class AsmTest { public static void main(String[] args) throws URISyntaxException, IOException { Path clsPath = Paths.get(AsmTest.class.getResource("/visitordp/User.class").toURI()); byte[] clsBytes = Files.readAllBytes(clsPath); // finalVisitor = DeleteFieldVisitor -> AddAnnotationVisitor -> ClassWriter ClassWriter cw = new ClassWriter(ClassWriter.COMPUTE_FRAMES); ClassVisitor finalVisitor = new DeleteFieldVisitor(new AddAnnotationVisitor(cw), "name"); ClassReader cr = new ClassReader(clsBytes); cr.accept(finalVisitor, ClassReader.SKIP_DEBUG | ClassReader.SKIP_FRAMES); byte[] bytes = cw.toByteArray(); Files.write(clsPath, bytes); }}Copy the code
By combining the visitor pattern with the chain of responsibility pattern, we no longer need to write all the logic in one visitor, we can split up multiple common visitors and combine them to meet more diverse needs.
Visitor pattern and callback pattern
“Callback” can be regarded as “design mode of design mode”, and its idea is found in many design modes, such as “observer” in observer mode, “command” in “command mode”, and “state” in “state mode”, which can be regarded as a callback function in essence.
The “visitors” in the visitor pattern is a callback, and other callback mode, are the main differences between “the visitor pattern is a kind of” with “navigation” callback, we through the incoming object structure to the implementer next callback “navigation”, the implementer according to the order of the “navigation” decide the callback.
If I want to visit fieldA first, then fieldB, and finally fieldC, the implementation to the visitor is:
visit(SomeObject someObject) {
someObject.fieldA.accept(this);
someObject.fieldB.accept(this);
someObject.fieldC.accept(this);
}
Copy the codeThe actual Application is HATEOAS (Hypermedia as the Engine of Application State). HATEOAS style HTTP interface will not only return the data requested by the user, but also contain the URL that the user should visit next. If the entire application API is like a home, if the user requests data for the living room, the interface will return not only data for the living room, but also the URL for the “kitchen”, “bedroom”, and “bathroom” connected to the living room:
The advantage of this is that resource urls can be seamlessly upgraded and changed (since they are returned by the server), and developers can learn to use the API by navigating without documentation, eliminating the problem of API organization. A more practical example of HATEOAS can be seen in How to GET a Cup of Coffee[1].
Vi Practical Application
The previous examples are probably more focused on the application of the open source base library, but how does it apply to a wider range of applications?
Complex nested structure access
Today’s toB applications provide increasingly complex configuration functions to meet the odd customization needs of different enterprises. Instead of simple orthogonal independent relationships, configuration items are nested recursively, which is where the visitor pattern comes into play.
The nailing approval process configuration is a very complex structure:
The simplified approval flow model is as follows:
The mapping between model and process configuration is shown below:
RouteNode not only connects the next node through next like a common node, but also has a complete process configuration (recursive definition) for each condition contained in RouteNode, so it can be seen that the approval node model is a complex nested structure.
In addition to the overall complexity of the structure, the configuration of each node is also quite complex:
In the face of such a complex configuration, it is best to resolve the complexity of the configuration of the binary package (hereinafter referred to as SDK) for application layer masking. If the SDK simply returns a graph structure to the application layer, the application layer will have to be aware of the association between nodes and write error-prone traversal algorithms every time, and the visitor pattern becomes our best choice.
The implementation of the visitor pattern is the same as before. Without further elaboration, let’s take an application layer example:
-
Simulation: Enables the user to see the execution branch of the process without actually running it, facilitating debugging
class ProcessSimulator implements ProcessConfigVisitor { private List< String> traces = new ArrayList<>();
@Override public void visit(StartNode startNode) { if (startNode.next ! = null) { startNode.next.accept(this); }} @override public void visit(RouteNode RouteNode) {for (CondtionNode conditionNode: routeNode.conditions) { if (evalCondition(conditionNode.condition)) { conditionNode.accept(this); } } if (routeNode.next ! = null) { routeNode.next.accept(this); } } @Override public void visit(ConditionNode conditionNode) { if (conditionNode.next ! = null) { conditionNode.next.accept(this); }} @override public void visit(ApproveNode ApproveNode) {addaddres (ApproveNode); if (approveNode.next ! = null) { approveNode.next.accept(this); }}Copy the code}
2 SDK isolates external calls
In order to keep the SDK pure, the external interface is not normally called in the SDK, but in order to fulfill some requirements, we can put the external call in the application layer visitor’s implementation, and then passed into the SDK to execute the relevant logic.
In the process simulation mentioned above, conditional calculations often include external interface calls, such as calling a user-specified interface through the connector to determine the process branch. To ensure the purity of the process configuration parsing SDK, calls that cannot be made in the SDK package are therefore made in visitors.
Use Java18 to implement the visitor pattern
Back to the original proposition, use the visitor pattern to get all function calls in SQL. As mentioned earlier, pattern matching is much easier to implement using patterns common in functional programming languages, and is well supported in the latest Java18.
Starting with Java 14, Java supports a new Record data type, as shown in the following example:
Num and Add sealed interface Expression {// record instead of class Record Num(int value) implements Expression {} Record Add(int left, int right) implements Expression {} }Copy the codeOnce a TestRecord is instantiated, the fields are immutable, and its equals and hashCode methods are automatically overridden, so long as the internal fields are equal, they are equal:
public static void main(String[] args) { Num n1 = new Num(2); // n1.value = 10; Num n2 = new Num(2); // true System.out.println(n1.equals(n2)); }Copy the codeMore conveniently, with the latest pattern matching feature in Java 18, you can unpick the properties:
public int eval(Expression e) {
return switch (e) {
case Num(int value) -> value;
case Add(int left, int right) -> left + right;
};
}
Copy the codeLet’s start by redefining our SQL structure using the Record type:
sealed interface SqlNode {
record SelectNode(FieldsNode fields, List< String> from, WhereNode where) implements SqlNode {}
record FieldsNode(List< Expression> fields) implements SqlNode {}
record WhereNode(List< Expression> conditions) implements SqlNode {}
sealed interface Expression extends SqlNode {
record IdExpression(String id) implements Expression {}
record FunctionCallExpression(String name, List< Expression> arguments) implements Expression {}
record LiteralExpression(String literal) implements Expression {}
record OperatorExpression(Expression left, String operator, Expression right) implements Expression {}
}
}
Copy the codeThen, using pattern matching, a single method can achieve the previous access and get all the function calls:
public List< String> extractFunctions(SqlNode sqlNode) { return switch (sqlNode) { case SelectNode(FieldsNode fields, List< String> from, WhereNode where) -> { List< String> res = new ArrayList<>(); res.addAll(extractFunctions(fields)); res.addAll(extractFunctions(where)); return res; } case FieldsNode(List< Expression> fields) -> { List< String> res = new ArrayList<>(); for (Expression field : fields) { res.addAll(extractFunctions(field)); } return res; } case WhereNode(List< Expression> conditions) -> { List< String> res = new ArrayList<>(); for (Expression condition : conditions) { res.addAll(extractFunctions(condition)); } return res; } case IdExpression(String id) -> Collections.emptyList(); case FunctionCallExpression(String name, List< String> res = new ArrayList<>(); res.add(name); for (Expression argument : arguments) { res.addAll(extractFunctions(argument)); } return res; } case LiteralExpression(String literal) -> Collections.emptyList(); case OperatorExpression(Expression left, String operator, Expression right) -> { List< String> res = new ArrayList<>(); res.addAll(extractFunctions(left)); res.addAll(extractFunctions(right)); return res; }}}Copy the codeComparing the code in section 2, the biggest difference is that SQLNode.accept (visitor) is replaced with a recursive call to extractFunctions. The other is that the behavior that used to be encapsulated by classes becomes a much lighter function. We will explore this in more depth in the next section.
Rediscover the visitor model
In GoF’s original design patterns, the visitor pattern is described as follows:
Represents an operation that operates on elements in an object structure. It allows you to define new operations on elements without changing their classes.
Can be seen from this sentence, all function is essentially the visitor pattern implementation can be realized by the method of adding new members to each object, using the characteristics of object-oriented polymorphism, call the parent structure and polymerization substructure method returns the results, corresponding to extract all the SQL function before, for example, this time without the visitor, Instead, add an extractFunctions member method to each class:
class SelectNode extends SqlNode { private final FieldsNode fields; private final List< String> from; private final WhereNode where; SelectNode(FieldsNode fields, List< String> from, WhereNode where) { this.fields = fields; this.from = from; this.where = where; } public FieldsNode getFields() { return fields; } public List< String> getFrom() { return from; } public WhereNode getWhere() { return where; } public List< String> extractFunctions() { List<String> res = new ArrayList<>(); // Continue to call extractFunctions res.addall (fields.extractFunctions()); res.addAll(selectNode.extractFunctions()); return res; }}Copy the codeThe visitor pattern essentially abstracts all member methods from a complex class hierarchy into a single class:
What’s the difference between the two? Although the name of Visitor looks like a noun, but from the previous examples and discussion, its implementation class is all about the operation of the abstract, from the pattern matching implementation can see this point, ASM even Visitor as a small operation of the abstract arrangement and combination, So the two ways of writing also correspond to two worldviews:
- Object orientation: The belief that operations must be bound to data, that is, exist as member methods of each class, rather than being extracted as a visitor
- Functional programming: Separate data from operations, permutations and combinations of basic operations into more complex operations, with one visitor implementation for each operation
These two methods, when written, look very different, and only become dramatically different when it comes time to add a modification function. Suppose we now add a new operation to each class:
This scenario seems more convenient for adding visitors. So in the next scenario, suppose we now want to add a new class to the class hierarchy:
The two scenarios corresponding to the two split ways of software, one kind is according to the data, one is in accordance with the function point, in ali each double tenth a breakout and function, for example: box of horses, hungry? And as a venue to participate in the bargain, double tenth of a promotion, they all need to offer coupons, order and payment, etc.
Although hema, Ele. me and Juhuasuan are three different applications in users’ eyes, the underlying system can be divided in two ways:
Any kind of division must bear the disadvantage that this kind brings. All real-world applications, whether architecture or coding, are less extreme than the above examples, but rather a mix of the two. For example, Hema, Ele. me and Juhuasuan.com all have their own systems and reuse coupons and other systems divided by functions. The same applies to coding. There is no silver bullet in software engineering, and it is up to us to decide whether to use object-oriented abstractions or visitor abstractions depending on the characteristics and scenario. More often than not, it is necessary to mix the two, using some core methods as object members and using the visitor pattern to implement the trivial and messy requirements of the application layer.
The original link
This article is the original content of Aliyun and shall not be reproduced without permission.