Constraint satisfaction and debugging for interactive user interfaces 论文

摘要

Many user interface toolkits use constraint solvers to maintain geometric relationships between graphic objects, or to connect the graphics to the application data structures. One efficient and flexible technique for maintaining constraints is multi-way local propagation, where constraints are represented by sets of method procedures. This dissertation examines the use of local propagation constraint solvers in user interface toolkits, and presents three new systems: (1) The SkyBlue constraint solver. SkyBlue is an incremental constraint solver that uses local propagation to maintain a set of constraints as individual constraints are added and removed. If all of the constraints cannot be satisfied, SkyBlue leaves weaker constraints unsatisfied in order to satisfy stronger constraints (maintaining a constraint hierarchy). SkyBlue is a more general successor to the DeltaBlue algorithm that satisfies cycles of methods by calling external cycle solvers and supports multi-output methods. These features make SkyBlue more useful for constructing user interfaces, since cycles of constraints can occur frequently in user interface applications and multi-output methods are necessary to represent some useful constraints. (2) The Multi-Garnet user interface development system. Garnet is a user interface toolkit that incorporates a constraint solver to maintain one-way constraints between object fields: any object field can have an associated formula to calculate its value from other object fields. The Multi-Garnet package extends Garnet to support multi-way constraints and constraint hierarchies. It integrates the SkyBlue solver into the Garnet object system, allowing programmers to create and use constraints without explicitly accessing the constraint solver. Multi-Garnet has been used to construct complex user interfaces that would have been difficult to construct just using Garnet's constraint solver. (3) The CNV user interface builder and debugger. Programmers need tools to examine the behavior of large constraint networks, just as they need such tools when debugging imperative programs. The CNV user interface builder includes a set of debugging tools to help programmers understand the behavior of complex constraint networks. One tool uses a new algorithm to generate alternate constraint solutions that would have been produced if SkyBlue had chosen different methods to satisfy the constraints.