PixieDust：静态依赖跟踪实现的增量用户界面渲染

7210PixieDust：通过静态依赖跟踪进行声明性增量用户界面渲染0Nick tenVeen荷兰代尔夫特理工大学，代尔夫特，荷兰n.tenveen@student.tudelft.nl0Daco C.Harkes荷兰代尔夫特理工大学，代尔夫特，荷兰d.c.harkes@tudelft.nl0EelcoVisser荷兰代尔夫特理工大学，代尔夫特，荷兰e.visser@tudelft.nl0摘要0现代Web应用程序是交互式的。反应式编程语言和库是声明性指定这些交互式应用程序的最先进方法。然而，使用这些方法编写的程序由于效率原因包含容易出错的样板代码。在本文中，我们介绍了PixieDust，一种用于基于浏览器的应用程序的声明性用户界面语言。PixieDust使用静态依赖分析在运行时增量更新浏览器DOM，无需样板代码。我们证明PixieDust中的应用程序包含的样板代码比最先进的方法少，同时实现了相当的性能。0ACM参考格式：Nick ten Veen，Daco C. Harkes和EelcoVisser。2018。通过静态依赖跟踪实现声明性增量用户界面渲染的PixieDust。在WWW'18Companion：2018年Web会议伴侣，2018年4月23日至27日，法国里昂。ACM，纽约，纽约，美国，9页。https://doi.org/10. 1145/3184558.318597801 引言0现代Web应用程序是交互式的。数据编辑不会触发页面重新加载，而是进行原地DOM更新。这些DOM更新可以手动编写，但这是一项繁琐且容易出错的工作。一种声明性但天真的解决方案是在每次编辑时从声明性渲染函数中重新构建整个DOM。然而，DOM操作很慢，因此这种方法会导致大型应用程序的界面不响应。此外，DOM元素将失去其本地状态（如焦点和事件处理程序）。当前最先进的声明性解决方案维护一个虚拟DOM，并根据虚拟DOM渲染之前和之后的视图之间的差异应用DOM更新。当数据被编辑时，这些解决方案会比较视图的差异并应用DOM更新来修补差异。由于计算两个树之间的最小差异是O(n^3)[5]，这些解决方案使用O(n)的非最小树差分算法。非最小树差分可能存在可扩展性问题，可以通过识别哪些子树在更改时需要更新来缓解。然而，程序员负责正确识别这些子树，这导致了样板代码。0本文根据知识共享署名4.0国际许可证发布。作者保留在其个人和公司网站上传播作品的权利，并附上适当的归属。WWW'18Companion，2018年4月23日至27日，法国里昂，©2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可证发布。ACM ISBN978-1-4503-5640-4/18/04。https://doi.org/10.1145/3184558.31859780在本文中，我们介绍了PixieDust，一种Web编程语言，通过编译时静态依赖分析自动推导出用于计算增量视图更新的代码，从而实现了用户界面的简洁声明性定义。本文的贡献如下：0•PixieDust语言的设计，支持对数据模型和视图进行简洁和声明性的定义。• 模型更新对视图的影响的静态依赖分析。•将PixieDust程序映射到JavaScript实现的增量视图更新，以React框架为基础。•评估结果表明，该方法的性能与最先进的方法相当，代码大小减少了2倍。0我们按照以下步骤进行。在下一节中，我们分析现有的解决方案，以查看引入了哪些容易出错的样板代码。在第3节中，我们提出了一种用于静态依赖跟踪的方法，以识别需要重新渲染的子树。在第4节中，我们介绍了PixieDust语言，用于指定数据模型和声明性视图，其中包含了这种静态依赖跟踪。在第5节中，我们正式定义了PixieDust的依赖分析。在第6节中，我们正式定义了PixieDust的操作语义，详细说明了它与浏览器的交互。在第7节中，我们评估了我们的语言设计，在第8节中，我们将PixieDust与相关工作进行了比较。02 现有方法0在本节中，我们分析了现代方法中用于高效更新DOM的技术，并确定了这些技术存在的问题。0状态1 状态20div0h1 p0div0h1 p div0图1：默认情况下，现有框架的差异算法按顺序比较子项。在前面添加一个子节点会导致所有子项完全重新渲染。可以通过手动为子项添加标识来解决此问题。0Track：Web编程WWW 2018，2018年4月23日至27日，法国里昂}type: TodoActionKeys.TOGGLE_TODO,todoId: todoId}? {finished: !todo.finished, ...}: todo);}}model}view}Track: Web Programming WWW 2018, April 23-27, 2018, Lyon, France7220

0{this.props.todos.map(todo =>0000

0图2：在MobX中，子项的标识（键）可以提高性能，但会增加样板代码。这适用于所有最先进的解决方案。0线性树差分。所有最先进的方法都使用线性树差分（例如React[2]）。线性树差分算法逐级递归地比较旧的和新的虚拟DOM树。如果节点的标签与先前版本相等，则浏览器DOM节点保持不变。比较保持不变节点的属性，并在DOM中修补任何差异。这些节点的子节点在下一级中遍历。如果标签不同，则整个节点及其子节点从DOM中删除并从头开始重建。当节点的子节点重新排序时，线性差分算法无法确定子节点的新位置。这意味着子节点不是重新排序，而是相互替换。这可能非常低效，例如当一个子节点作为第一个子节点添加时（图1）。为子节点添加标识可以在线性时间内重新排序（图2）。然而，程序员有责任找到适合使用的数据结构的合适标识，并将其绑定到其子树。0识别DOM树中需要更新的部分。当整个树的某些部分不依赖于所做的更改时，无需对整个树结构进行差异比较。如果子树由其依赖的值集合参数化，则可以使用这些信息仅在这些值更改时进行差异比较。有多种方法可以实现这一点。第一种方法是使用不可变数据。Elm[4]和Redux[3]使用这种方法。使用不可变数据结构和纯视图函数，可以使用引用相等性来确定是否需要重新渲染子树。当值发生变化时，只有显示该值的节点和到树根的路径会重新计算。由于不可变数据结构不能包含循环，程序员需要使用树形数据模型。由于不可变数据不能就地更新，使用不可变数据的解决方案使用消息传递来编码更新。这些消息被分派到一个纯函数，该函数根据先前的状态计算新状态。这种优化确实带来了很多样板代码：每个操作都需要在数据结构中进行编码，当这些操作被解码时，需要查找并修改状态的相关部分（图3）。本地化DOM差异比较的另一种方法是为视图构建一个依赖图。这样，视图可以观察对其依赖项进行的写操作以触发重新渲染。因此，对数据的设置调用会自动反映在用户界面中。MobX[1]是一个在渲染时动态构建依赖图的框架。为了在运行时实现这一点，MobX依赖于对数据的get和set操作进行包装。然而，0enum TodoActionKeys{ TOGGLE_TODO = "TOGGLE_TODO" } interfaceToggleTodoAction{0type: TodoActionKeys.TOGGLE_TODO, todoId:string0} type TodoAction = ToggleTodoAction0function toggleTodo(todoId: string) {0return {0} function reducer(todos:Todo[], action:TodoAction){0switch (action.type){0case TodoActionKeys.TOGGLE_TODO:0return todos.map(todo =>0todo.id == action.todoId0图3：在Redux中调度状态更新所需的样板代码。该操作被编码为一个普通的JavaScript对象，由运行时传递给处理所有可能操作的纯函数。0entity TodoList {0todos: Todo* (inverse = Todo.list)0} entity Todo {0description: String finished:Boolean0TodoList.view = div { ul { todos.itemView } }0Todo.itemView = li {0input [ type="checkbox", value=finished ] span {description }0图4：迷你ToDo应用程序数据模型和视图0这可能会导致一个子组件被传递一个值而不是该值的getter的微妙错误。0总结。总之，所有最先进的解决方案都会引入容易出错的样板代码。所有解决方案都需要在列表上添加标识。不可变数据解决方案（Elm和Redux）需要将数据修改编码为操作对象，可变数据解决方案（MobX）捕获getter和setter（在JavaScript中可能会意外绕过）。view}}}}}}view}Track: Web Programming WWW 2018, April 23-27, 2018, Lyon, France72303 静态依赖跟踪0现有的客户端应用程序框架会引入容易出错的样板代码，并且它们的假设可能会被意外违反，导致隐含的错误。我们提出使用静态依赖跟踪作为解决这些问题的方法。静态依赖跟踪不会在运行时捕获getter和setter（例如MobX），而是在编译时（过度）近似依赖结构。视图定义引用数据模型的部分。这些引用可以在静态确定，并且可以用于决定在数据修改后应该重新渲染哪些视图。为了说明如何静态推导依赖关系，我们考虑一个迷你的ToDo应用程序（图4）。一个TodoList可以包含零个或多个Todo。一个Todo有一个描述和一个完成标志。TodoList的视图是一个包含每个项目的li的ul。每个Todo都以复选框表示完成状态和以span表示描述。通过分析视图的内容，我们可以收集所有引用的路径。itemView引用了Todo的两个字段。TodoList.view引用了它的todos的itemView。这意味着当引用的itemView发生变化或todos列表本身发生变化时，需要更新此视图。综上所述，应用程序包含以下依赖关系：0Todo.itemView <- finished Todo.itemView<- description TodoList.view <- todosTodoList.view <- todos.itemView0这些依赖关系可以被反转以获得应用程序的数据流。为了能够反转引用todos的依赖关系，我们需要一个inverse。图4将todos的inverse定义为Todo.list。当我们反转依赖关系时，我们得到以下数据流：0Todo.finished -> itemView0Todo.description -> itemViewTodoList.todos -> view0Todo.itemView -> list.view0这种数据流可以用于在数据修改时触发视图的重新渲染。此外，由于视图是由实体参数化的，我们可以自动为集合分配键，而不需要冗余的样板代码。我们已经设计并实现了PixieDust，这是一种基于这种依赖分析的在浏览器中声明性定义用户界面的新语言。我们将在第5节中形式化这种依赖分析，但首先我们将讨论PixieDust的设计。04 PixieDust0PixieDust是一种用于指定数据模型和基于浏览器的用户界面的语言，通过关键字（例如图4）将模型和视图的关注点分离开来。数据模型中定义的所有内容都在视图中可见，但反之则不然。0数据模型。对于数据模型，我们使用现有的IceDust数据建模语言[7,8]。在IceDust中，数据模型由实体和字段组成。所有字段都有一个类型和一个多重性。IceDust中的多重性为1、?、�和+（类似于正则表达式，并在示例中以红色突出显示）。如果省略多重性，则默认为1。具有实体类型的字段具有一个inverse。当一个对象从这样的字段引用到另一个对象时，0TodoList {0view : View = div {0header ul { visibleTodos.itemView }footer0header : View = div {0h1 { "Todos" } input [ type="checkbox", value=allFinished,0onClick=toggleAll ]0StringInput [ onClick=addTodo ](input)0footer : View = div {0todosLeft "items left" ul {0visibilityButton(this, "All") visibilityButton(this,"Finished") visibilityButton(this, "Not finished")0} if (count(finishedTodos) > 0)0button [ onClick=clearFinished ]0} Todo {0itemView : View = li { div {0BooleanInput(finished) span { task } button [onClick=deleteTodo ] { "X" }0图5：TodoList视图：TodoList视图有一个带有输入字段的标题，用于添加新的待办事项；一个包含所有待办事项的列表；以及一个显示剩余待办事项数量、用于筛选要显示的待办事项的过滤器，以及一个用于删除已完成待办事项的按钮的页脚。0TodoList {0input: String = (init = "")0show: String = (init = "All")0finishedTodos: Todo* =0todos.filter(todo => todo.finished)(inverse =Todo.inverseFinishedTodos?)0visibleTodos: Todo* =0switch {0case show == "All" => todos0case show == "Finished" => finishedTodos default =>todos \ finishedTodos0} (inverse = Todo.inverseVisibleTodos?)0图6：TodoList视图状态：视图状态包含一个字段用于存储添加新项目的输入，一个字段用于过滤可见项目，以及用于计算可见项目的字段。view}addTodo:toggleAll: todos.finished := !allFinishedclearFinished: todos −= finishedTodossetVisibility(to: String): show := to}}Figure 7: ToDo application actions: items can be toggled,deleted and added; and for a list all items can be toggled, allfinished items can be deleted, and the filter can be changed.the other object refers back from its inverse field. Lastly, IceDustfeatures derived value fields: fields for which the value is calculated.For example, we can extend the TodoList in Figure 4 with a fieldindicating whether all todos are finished and how many are left:entity TodoList {allFinished : Boolean = conj(todos.finished)todosLeft: Int = countFalse(todos.finished)}View. In PixieDust we define views in the context of an entity(Figure 5). The View type is a (virtual) DOM node. Inside a view, thefields of the context entity can be concisely accessed by referringto them. Other views of the same entity also can be referenceddirectly, and views of other entities can be referenced by memberaccess. This makes for concise definitions of views in PixieDust.The view of a model might contain state. In our example wehave the state of the input field for adding new todos. To separatethe concerns of data model and view, we do not add this state tothe data model, but introduce view state. View state fields can be ofany type and are scoped by a context entity (Figure 6). View statesupports the same kind of derived values as the data model. Forexample we derive the visible todos collection in Figure 6.User interfaces should support user interaction with the applica-tion. In PixieDust, actions declaratively describe data modification(Figure 7). Actions are also scoped by an entity, this makes for con-cise definitions. Both the data model and view state can be accessedwithin actions. Moreover, new objects can be created (see addTodo)and old objects can be left for garbage collection (see deleteTodo).Often an input element reads and writes to a specific field ofan entity. One could program an action for each field, but that istedious. For concise UI specifications, a language should supportbidirectional mappings between user interface and data model.PixieDust provides built-in bidirectional mappings for primitivefunctionsvisibilityButton(l:TodoList, to:String):View =li[onClick = l.setVisibility(to)] { to }countFalse(bs : Boolean*) : Int =count(bs.filter(b => !b))Figure 8: Functions in ToDo application facilitate reusedata types (BooleanInput and StringInput in Figure 5). In futurework we would like to explore user-defined bidirectional mappings.Example. Figures 4-7 contain an almost complete specification ofa full ToDo application in PixieDust. The only thing missing is thedefinition of two functions (Figure 8). Together, these figures forma concise specification of a complete ToDo application. Moreover,this application is incremental: derived values are only recalculatedand views are only rerendered when needed.5DEPENDENCY AND DATA-FLOW ANALYSISIn Section 3 we introduced static dependency tracking as a way toget rid of error-prone dynamic dependency boilerplate code. In thissection we formalize this static dependency analysis. The analysisis based on the dependency analysis of IceDust [7]. In this paperwe extend it with analysis for functions and views.Dependencies between Fields in Data Model. First, we recap theanalysis of dependencies between fields from IceDust. To illustratethe analysis we extend Figure 4 with allFinished which is theconjunction of the finished fields:allFinished : Boolean = conj(todos.finished)The dependencies of a field are all fields which are needed to com-pute the derived value of that field. The dependencies are reachablefrom the entity containing the field via a path. A dependency isdenoted by (Ent.Field ← π), where Ent.Field is a field and π is thepath to a field.Computing the dependencies requires extracting paths fromexpressions defining field values. The path-based abstract inter-pretation relation (Figure 9) defines the dependency paths of anexpression. We use the notation (Expr ↘ {π}{ρ}), where Expr isthe expression that is abstractly interpreted, and {π} and {ρ} arethe sets of paths defined by the abstract interpretation. The pathsin {π} are extended by surrounding expressions, while the pathsin {ρ} are not. The if only extends paths in the second and thirdoperand, so Π1 is passed to {ρ}. All paths start with this [This] orwith navigation [NavStart]. When navigating by means of e.m alldependency paths in {π} are extended with .m [Nav]. Operatorsjust pass on all paths [UnOp, BinOp], and literals do not contain anypaths [Literal]. Path-based abstract interpretation of the expressiondefining allFinished produces a set with a single path:{ todos.finished }The dependencies relation (Figure 9) defines the dependencies ofa field and a full program. We use the notation Field|Proд ↘↘{(Ent.Field ← π)} where Field|Proд is a field or full program, and{(Ent.Field ← π)} is a set of dependencies. When a field dependson the value at the end of a path, it also depends on the relations enTrack: Web Programming WWW 2018, April 23-27, 2018, Lyon, France7240Todo {0actions {0toggleTodo: finished: = !finished deleteTodo:list: = null0} TodoList {0actions {0todos += { description = input0finished = false0input: = ""Path-based abstract interpretationExpr ↘ {π }{ρ }m ↘ {m}{}[NavStart]e ↘ Π Pe . m ↘ {π .m | π ∈ Π} P[Nav]this ↘ {this}{}[This]e ∈ Literale ↘ {}{}[Literal]⊕ ∈ U nOpe ↘ Π P⊕ e ↘ Π P[UnOp]⊕ ∈ BinOpe1 ↘ Π1 P1e2 ↘ Π2 P2e1 ⊕ e2 ↘ Π1 ∪ Π2P1 ∪ P2[BinOp]e1 ↘ Π1 P1e2 ↘ Π2 P2e3 ↘ Π3 P3e1?e2:e3 ↘ Π2 ∪ Π3Π1 ∪ P1 ∪ P2 ∪ P3[If]⊕ ∈ {filter, find, orderBy}e1 ↘ Π1 P1e2 ↘ Π2 P2Π′2 =replace-id*(Π2, x, Π1)P′2 =replace-id*(P2, x, Π1)e1. ⊕ (x => e2) ↘ Π1Π′2 ∪ P1 ∪ P′2[Col]f .expr ↘ Πf Pfei ↘ Πi PiPe = �i=1..n PiΠnamede= {(f .args[i], Πi) | i ∈ 1..n}Π′f =replace-ids(Πf , Πnamede)P′f =replace-ids(Pf , Πnamede)f (e1, . . . , en) ↘ Π′fP′f ∪ Pe[Fun]replace-id(x.π, x, π2) = π2.πreplace-id(π, x, π2) = πreplace-id*(Π1, x, Π2) = {replace-id(π1, x, π2) | π1 ∈Π1, π2 ∈Π2 }replace-ids(Π1, []) = Π1replace-ids(Π1, [(x, Π2)|t]) = replace-ids(replace-id*(Π1, x, Π2), t)DependenciesField |Proд ↘↘ {(Ent .Field ← π)}m.expr ↘ Π Pe = m.entityΠ2 = � {trans-pref(remove-this(π)) | π ∈ Π ∪ P}m ∈ Field ↘↘ {(e.m ← π) | π ∈ Π2}[Field]Π = � {dep | m ↘↘ dep, m ∈ e.fields, e ∈ p.entities}p ∈ Proд ↘↘ Π[Prog]remove-this(this . π) = πremove-this(m . π) = m . πtrans-pref(π . m) = {π . m} ∪ trans-pref(π)trans-pref(m) = {m}(TodoList.allFinished ← todos.finished)(TodoList.allFinished ← todos)2 =.(e1 . m1 ← π . m2) ↗ (e2 . m2 → inv-path(π) . m1)[InvDep]inv-path(π . m) = m−1 . inv-path(π)inv-path(m) = m−1inv-path(null) = null↘↘p ∈ Proд ↗↗ {df | dep ↗ df , dep ∈ Dep }[Prog](TodoList.todos → allFinished)(Todo.finished→ list.allFinished)numLeft:Int = count(todos.filter(x=>!x.finished)){ todos.finished }todosLeft : Int = countFalse(todos.finished)function countFalse(bs : Boolean*) : Int =count(bs.filter(b => !b)){ bs }7250图9：通过路径提取定义的依赖关系0路由。因此，字段[Field]的规则采用其表达式的路径的传递前缀。由于路径后来被连接，所以路径中的this被移除。我们示例的路径如下：0从字段到计算其值的所有字段的数据流是依赖关系的逆。我们使用(Ent . Field  →  π )来表示数据流0依赖反转 ( Ent  . Field  ←  π ) ↗ ( Ent  . Field  →  π )0数据流 Proд  ↗↗ {( Ent  . Field  →  π )}0图10：通过反转依赖关系的数据流关系0从源Ent . Field到目标路径π的数据流关系。图10中的依赖反转关系(Ent . Field  ←  π ) ↗ ( Ent . Field  →  π)定义了依赖的逆。通过交换源和目标来逆转依赖关系，并反转路径π以获得从目标到源的路径。函数inv-path( π)反转路径上的名称并反转它们的顺序。名称反转是选择双向关系的对立面上的名称。我们示例中的结果数据流如下：0带有Filter、Find和OrderBy的依赖关系。请注意，IceDust 2[8]引入了filter、find和orderBy，但没有为它们提供依赖分析的文档。为了说明这些的分析，考虑将以下内容添加到TodoList中：0规则[Col]（图9）涵盖了包含lambda的这些表达式。lambda主体中参数x的路径的出现被替换为调用点参数的路径。对于我们的示例，将x.finished中的x替换为{ todos }的路径如下：0带有函数的依赖关系。在本文中，我们扩展了支持函数的依赖分析。作为函数的示例，我们使用了一个用于计算等于false的元素数量的函数来指定todosLeft：0图9中的规则[Fun]涵盖了用户定义函数。函数调用的依赖路径被定义为函数定义表达式的依赖路径，其中所有参数名称的出现都被调用点参数的路径替换。请注意，这些都是路径集合，因此函数replace-id*和replace-ids操作的是集合。如果我们将分析应用于我们的示例，函数主体的路径如下：0Track: Web Programming WWW 2018, 2018年4月23日至27日，法国里昂�����C ∈����Q ∈ Queue : {ComponentRef }F ∈ Frame : ObjectRef( bs => { todos.finished } ){ todos.finished }entity Node {children : Node* (inverse = Node.parent?)cnt : Int = count_descendants(this)}function count_descendants(n : Node) : Int =count(n.children) + sum(n.children.cnt)Σ2 = Σ[o, f , dirty �→ true][schedule(c) ⇓ | c ∈ Σ[o, f ].subs]o.flagDirty(f )/Σ ⇓ /Σ2[FlagDirty]Q2 = Q ∪ {c }subscribe() ⇓schedule(c)/Q ⇓ /Q2[Schedule]F = nullF2 = requestAnimationFrame(s))subscribe()/F ⇓ /F2[SubFrame1]F � nullsubscribe() ⇓[SubFrame2][c.forceUpdate() ⇓ | c ∈ Q, C[c, mounted]=true]Q2 = ∅unsubscribe() ⇓onAnimationFrame(s)/Q ⇓ /Q2[Render]F�nullcancelAnimationFrame(F)F2 =nullunsubscribe()/F ⇓ /F2[UnsubFrame1]F = nullunsubscribe() ⇓[UnsubFrame2]Track: Web Programming WWW 2018, April 23-27, 2018, Lyon, France7260Σ  ∈  Entity  :  EntityRef  ×  Field