MatchToolDoc.tioga
Copyright Ó 1988 by Xerox Corporation. All rights reserved.
Kurlander, September 4, 1987 1:40:09 pm PDT
Bier, November 13, 1987 6:01:12 pm PST
Pier, August 19, 1988 6:17:47 pm PDT
MatchTool
CEDAR 7.0 —
Match Tool
Graphical Search and Replace
David Kurlander
© Copyright 1987, 1988 Xerox Corporation. All rights reserved.
Abstract: The MatchTool is a utility for performing graphical search and replace operations, supplementing the graphical editing capabilities of the Gargoyle illustrator. It is the Gargoyle illustrator's analog to the Tioga editor's EditTool. In its simplest form, MatchTool can be used to find all instances of a graphical object in a Gargoyle scene, and replace them with another graphical object. However, MatchTool will also permit searches on arbitrary sets of graphical attributes and replacements by other sets of attributes. In addition to being of use in common graphical editing scenarios, this function can be used to create complex shapes formed by graphical grammars. MatchTool also has a simple facility for defining graphical macros. MatchTool's graphical grep capability can be used to search for Gargoyle scene files which contain a particular graphical pattern.
Created by: David Kurlander
Maintained by: <GargoyleImplementors^.pa>
Keywords: Graphical Search, Graphical Replace, Substitution, Gargoyle, Pattern Matching
XEROX  Xerox Corporation
   Palo Alto Research Center
   3333 Coyote Hill Road
   Palo Alto, California 94304
1. Introduction
The MatchTool viewer contains a variety of subviewers, labels, and buttons. Below we have a description of them and their functions. Following this, search, replace, macros and graphical grep are each discussed in terms of what the user must know in order to use MatchTool.
2. The MatchTool Viewer
At the top of the MatchTool viewer are two Gargoyle subviewers. The left subviewer is called the Search viewer, since the search attributes are taken from this viewer. The Search viewer is the analog of the EditTool's Target field. The search pattern is drawn here.
To the right of the Search viewer is the Replace viewer. The Replace viewer gets its name from the fact that graphical attributes in this window are applied to the match when a substitution is made. Essentially the Replace viewer is analogous to the EditTool's Replacement field.
These two subviewers have the full editing capability of Gargoyle, with the exception of certain operations which can only be invoked via the Gargoyle menu. Unfortunately, there's not enough room for a full Gargoyle menu on the MatchTool viewer, so MatchTool has to share some of the important menu buttons with a Gargoyle viewer. As a result, a Gargoyle viewer must be invoked prior to running the MatchTool.
Note: the Search and Replace viewers do not have Gargoyle history tools associated with them. One level of Undo, bound to the SHIFT-ESC command, is available in the Search and Replace viewers.
Immediately below each of the Gargoyle subviewers is a set of buttons. The Fetch button fetches selected objects from the Gargoyle viewer that has the input focus into the Gargoyle subviewer associated with this button. The location of the input focus determines the source Gargoyle viewer for this operation. Objects which are fetched into one of the subviewers are placed at the same coordinates as the original, and may potentially be off-screen.
The Fit, Reset, and CenterSel buttons control the extent of the Gargoyle scene which is shown in the subviewer. Fit scales the BiScrollers viewer so that the entire scene is visible. Reset places the BiScroller back into its initial configuration. CenterSel translates the BiScrollers viewer so that the selected objects in the Gargoyle scene are centered. After fetching an object into one of the Gargoyle subviewers, it usually makes sense to hit either the Fit or CenterSel buttons, since it is quite probable that the object was fetched into a non-visible portion of the Gargoyle subviewer. Keep in mind that though the Search and Replace viewers seem to be smaller than typical Gargoyle viewers, they are really BiScrollers, and can contain scenes which are as large as any other Gargoyle scene.
The Characteristics button columns are used in order to specify which graphical attributes will participate in the search and replacement. They include:
Shape: The shape of the curve, which is independent of the object class and curve types of the graphical primitives which compose the curve.
Object class: The class of Gargoyle graphics object, otherwise known as "slice class." Gargoyle slice classes include outline, text, box, circle, and others.
Curve type: Really segment (curve) type. Gargoyle segment types include line, arc, conic, bezier, natural spline, and B-spline.
Area color: The color of the interior of the shape. By Gargoyle convention, this includes text color.
Line color: The color of the outline of the shape (line color).
Line width: The thickness of the line stroke.
Line dashes: The line stroke pattern.
Line joints: The manner in which the joints between contiguous segments are drawn. Can be rounded, mitred, or beveled.
Line ends: The manner in which the ends of lines are drawn. Can be rounded, squared, or butted.
Text string: The sequence of characters which form the text (for example, the letters h-e-l-l-o in "hello").
Text font: The font of the text, not including its point size (for example, helvetica).
Text font & transform: Both the font of the text and the associated transform which gives scaling and rotation information.
To the right of the listing of these graphical attributes on the MatchTool viewer are two button columns: The Search column and Replace column. The Search column specifies the set of attribute types which will participate in the search. The Replace column specifies those attribute types which will be used in the replacement. If several buttons in the Search column are turned on, then only objects matching all of the corresponding characteristics in the Search subviewer will be selected as a match. Similarly, the Replace column specifes which attributes of the objects in the Replace viewer to endow on the match (provided a substitution is being made). Basically, the Search and Replace button columns specify a set of attribute types, and the values of these attributes are taken from the objects in the Search and Replace viewers.
To quickly clear all of the buttons in the Search or Replace columns, left-click over the Search or Replace buttons. To set all the buttons in a column, right-click over the appropriate button.
On the right-hand side of the MatchTool control panel are the Find, Yes, No, and ChangeAll buttons. The Find button will initiate a search for the graphical pattern specified in the Search viewer and column. The search proceeds in either a downward direction from the caret (left-click), an upward direction from the caret (right-click) or from the very top of the viewer (middle click). The Yes button causes a replacement action (either a traditional replace or a macro operation) to be invoked on the last match. The search then proceeds in a direction dependent on which mouse button was pressed (see Find button, above). The No button specifies that no replacement operation is be performed on the current match, but the search is to continue in the direction determined by the mouse-click. The ChangeAll performs the replacement operation on all further matches in the scene, either all matches below the caret (left-click), above the caret (right-click), or all matches (middle click).
The Action button specifies the type of replacement action to be performed. If the replacement action is Do Replace, then the graphical attributes specified in the Replace column and subviewer will be given to the match. However, if the Do Operations action is set, then the Replace subviewer and column are ignored and the user-defined macro operation is invoked on the match.
The granularity of the search is controlled by the Granularity level button. If the granularity is set to Cluster Level, then only entire slices which match slices in the Search viewer will be found by the search. If Trajectory Level is set, then only entire trajectories which match trajectories in the Search viewer are valid matches. However, if the match level is Anywhere, then the MatchTool searches for the graphical pattern anywhere in the scene.
The SearchOp button specifies the manner in which the objects in the Search window are interpreted. If SearchOp is set to Disjunction, then any object in the scene which matches at least one of the objects in the Search viewer is considered a match. If SearchOp is set to Conjunction, then only entire collections of objects in the scene which match the entire set of objects in the Search viewer are considered matches.
The control panel line below this adjusts the tolerance of shape matches. If the Exact button is set (reverse video feedback), then shape matches will only pick out perfect shape copies of the pattern. However if the Exact button is turned off (toggle with any mouse click), then the Tolerance slider can be used to adjust the sensitivity of shape match. Moving the Tolerance slider to the right (by successive right button mouse clicks) permits shapes which are less alike, with respect to MatchTool's built-in shape metric, to match. Successive left clicks on the slider will decrease the tolerance, causing matches only on more alike shapes.
The RotationInv and ScaleInv buttons also affect the shape matching criteria. If RotationInv is set, then shape matches are rotation invariant, and shapes which are equivalent under a rotation are considered matches. The ScaleInv button can make a shape match scale invariant, thus two shapes which are identical except for size will be considered equivalent. If both the RotationInv and ScaleInv buttons are on, then shapes which are equivalent except for rotation and scale will match. All shape matches are invariant with respect to translations.
Segments and trajectories in Gargoyle have polarity, that is they each have a low end and a high end. If the Polarity button is set, then MatchTool will only try to match objects such that their polarities are aligned. If Polarity is off, then MatchTool will first try to match two objects so that their low ends are aligned, but failing that it will attempt a match that does not preserve polarity.
Next to the polarity is a button by which we can optionally turn on context-sensitive searches. During most searches the ContextSensitive button should be turned off, and the entirety of a match will be selected. During a context-sensitive search however, though a search will be made on the entire contents of the Search window, only the part of the match corresponding to a selected object in the Search window will be itself selected and considered a match. Context-sensitive searches in MatchTool are similar to search patterns in the EditTool that have the magical '{ }' characters.
In order to start a macro definition, hit the StartOps button. All Gargoyle edit operation in the Replace viewer will be recorded until the EndOps button is pressed. For macro operations to be performed instead of substitutions, make sure that the Action button is set to Do Operations.
The Grep button can be used in order to search for Gargoyle scene files that contain a particular graphical pattern. The graphical pattern should be specified in the Search viewer and column as it is for ordinary searches, and a filename pattern (including wildcards if desired) should be selected in a Tioga viewer. Right-clicking on Grep will list the names of files that match, writing this information in the Commander viewer which invoked the MatchTool. Left-clicking on Grep will open a Gargoyle viewer on the first matched file. The first match in the file will be selected. In order to move on to other Gargoyle scene files that match, the NextFile button can be pressed. If the last Gargoyle viewer which was invoked with the Grep mechanism has not been edited, then the next match will be loaded into this viewer. Otherwise a new viewer will be created.
3. Details of the Search
Search proceeds either an upwards or downwards fashion from the caret in the scene. Slices are searched in the order determined by the upper left corner of their boundbox. This makes downward searches a bit more intuitive. We've chosen to order upwards searches by the upper left corner of the boundbox also, since in this way reversing the order of the search will result in searching the objects in the exact reverse order of a forward search. If two slices have boundboxes beginning at the precise same upper Y value, and we're searching downwards in the scene, then we'll examine the left-most slice first. This reinforces the text searching metaphor (up-down, left-right vs. down-up, right-left).
Within a slice, search proceeds in a manner determined by the internals of the object. Thus, search may not proceed in an exactly up-down or down-up manner. Searching within a slice has been ordered to minimize the amount of mental context-switching that the user has to undergo. For example, we have chosen to complete searching an entire trajectory before moving on to the next. Since it may turn out that replacement decisions are frequently made on a trajectory by trajectory basis, this is probably a good idea, because the user will only need to consider a given trajectory once. Search within a trajectory is done in order of increasing segment number. If the match level is set to Anywhere, then we try to match the longest contiguous sequence of segments starting with the first segment of the trajectory. If this match fails, we match against the sequence with one fewer segments starting at this same segment, and continuously match against smaller sequences of segments until we get a match. If we don't find a match starting at the first segment of a trajectory, then we proceed to the next segment and continue to search in the same manner.
When the search is begun, a snapshot is taken of the scene, and only items that are in the snapshot will be potential matches. This means that objects that are added to the scene via the replacement mechanism cannot be matched until the search state is reset. The search state is recalculated the next time that one of the search buttons is hit if any of the following conditions is true:
1) The direction of search has switched.
2) The caret has been moved (by the user, not by MatchTool).
3) The last search was in a different Gargoyle viewer.
4. Details of the Replacement
There are cases in which it is not clear how to give a match certain attributes without giving it others as well. For example, what would it mean if I were to give a straight line segment the shape of a circle without changing its object class? In order to avoid deep philisophical issues such as this, we have chosen to make it impossible to change an object's class, type (that is, curve type), or shape without changing the other two. Pressing the class, type, or shape buttons in the Replace column will result in toggling all three buttons.
Knowing this you can understand a bit more about how replacements work, and particularly why some replacement specifications might be ambiguous. If the class, type, and shape buttons are not selected in the Replace column, then when a replacement is made, the characteristics which are selected in the Replace column are transferred directly to the match. Potentially there might be more than one value in the Replace viewer for an attribute type that has been selected in the Replace column. Since it wouldn't be clear which objects in the match should get which values of this attribute, the replacement is ambiguous, and the MatchTool will warn that this is the case by an appropriate message in its feedback line. As an example, if we wanted to change only the color of the match, so the color button was selected in the Replace column, it would be ambiguous to have several items in the Replace viewer with different colors.
However, there's a related case where ambiguous replacements might appear. If the class, type, and shape buttons are selected, that means that the objects in the Replace viewer are copied, given certain attributes from the matched objects (those attributes which are not selected in the Replace column) and placed in the Gargoyle scene. In this case, if the original matched objects in the Gargoyle scene have several different values for an attribute that is not selected in the Replace column, then the replacement will also be ambiguous. Again, if a replacement is ambiguous, a message to that effect will be displayed in the MatchTool feedback line.
If a class, type, and shape replacement is made, then the positioning of the replacement in the scene is important. Again, there are two cases. If a shape match was made, then MatchTool has determined a mapping between the coordinate system of the Search viewer and the coordinate system of the Gargoyle scene being searched. The mapping indicates what sort of translation, rotation, and scaling must be done in order to align the shape in the Search viewer with the shape of the match in the Gargoyle viewer. If a class, type, and shape replacement is being made, then this same transformation will be applied to the contents of the Replace viewer when copying it into the Gargoyle scene. This has two important ramifications. Firstly, it is important to understand that the replacement undergoes the same mapping transformation as the successful shape match, and thus will be oriented accordingly. For example, if we do a rotation and scale invariant shape match on all vertical lines, and change them to plus signs, then all diagonal lines in the scene will be changed to X's.
Another important result of this particular replacement mapping is that the user has to be aware of the spacial relationship between the Search and Replace viewers. Since the Search and Replace viewers each have scroll bars, the fact that two objects appear to be roughly in the same place with respect to the Search and Replace viewers does not imply that they are located in the same place with respect to their coordinate systems. If you want to make sure that a vertical line will be replaced by a plus sign IN THE SAME PLACE, make sure that you know the plus sign is located in the same place in the Replace coordinates as the vertical line is in the Search coordinates. The best way of assuring this would be to fetch a vertical line into the Replace viewer from the Search viewer, and to construct the replacement pattern from it.
However if a shape match was not performed, then MatchTool has no information as to a coordinate system mapping between the Search viewer and the Gargoyle scene. It needs to make a guess as to the desired positioning. Currently in this case we center the replacement over the location of the match. Since this replacement transformation is more arbitrary than the one previously described, MatchTool will flash a warning message when it is used. Eventually we may add several replacement alignment options to be chosen from the MatchTool control panel.
5. Explanation of the Macro Facility
Macros work in the following way. Between the time that StartOps and EndOps are pressed, a copy of events that occur in the Replace viewer are recorded by the MatchTool. Later when a match is found, the mouse coordinates of the saved events are transformed by the mapping transformation produced by the search, and these are played back in the Gargoyle scene. The mapping transformation was described in the previous section, and it can be either a precise shape transformation if the search included the shape attribute, or a transformation that centers the replacement over the match. If we were not matching on shape, then this centering correspondance carries with it little information as to the position of the object in the Gargoyle scene with respect to the object in the Replace viewer. Thus it would make little sense to transform the original mouse events by only a centering transform, and it would undoubtedly produce unpredictable results. These 'mouse-click macros' are only useful when there's a a shape transformation which fairly precisely maps an object in the Search viewer to the scene being searched, so the MatchTool macros should probably be used only in conjunction with searches that include the shape attribute.
Even when using the macros in conjunction with a shape search, there's a potential for unexpected results, since the Gargoyle scene in all probability contains more objects than the Replace viewer in which the macro was defined. Mouse clicks made in the Replace viewer, when transformed back into the Gargoyle scene, may be close to other objects. Thus it may make sense to turn gravity off prior to a search and macro replace. Macros in the MatchTool should only be used by experienced users. We can improve the mechanism by modifying the scene and alignment structures to include only the matched objects prior to invoking the macro, thus eliminating the potential for mishap. Afterwards, we would restore the scene to its proper updated state. But this improvement has yet to be implemented, so beware of macros, my son, the jaws that bite, the claws that catch. They make Bandersnatches look like Easter bunnies.
6. Graphical Grep
The graphical grep function is a mechanism for finding Gargoyle scene files by content instead of by name. Initially set up the MatchTool control panel as if you were planning on doing an interactive search in a single Gargoyle viewer. Select a filename pattern in a Tioga viewer (optionally including wildcards), and hit the Grep button. Messages will be written to MatchTool's feedback line indicating whether MatchTool is loading a file, searching in it, and whether it finds a match. If the mouse was right-clicked on Grep, then the names of the files which match the pattern will also be printed in Commander viewer which invoked the MatchTool. If the mouse was left-clicked on Grep, a Gargoyle viewer will be created, and loaded with the first file that matches the pattern. The first match found in the file will be selected. To investigate other potential file matches, hit the NextFile button. If the last Gargoyle viewer created by the Grep mechanism has been edited, a new Gargoyle viewer will be created and loaded with the next match; however, if that Gargoyle viewer has not been edited, the next file that matches will be loaded there.