Debian Codegraph @

doc/hacking-search.html

raw
1 <html>
2 <head>
3 <title>netrik hacker's manual: text search</title>
4 </head>
5 <body>
6
7 <h1 align="center">netrik hacker's manual<br />>========================&lt;</h1>
8
9 <p>
10 [This file contains a description of the text search functionality. See
11 hacking.txt or <a href="hacking.html">hacking.html</a> for an overview
12 of the manual.]
13 </p>
14
15 <a name="framework" id="framework">
16
17 <h2>Framework</h2>
18
19 <p>
20 Though by far not as complicated as link handling, the text search
21 functionality is also somewhat distributed: The serach command is given in the
22 pager (<a href="hacking-pager.html#display">display()</a>, see
23 hacking-pager.*), and after the search the new position is also activated here.
24 The search itself however is done in main(). (There is no real reason for this,
25 except that reading the search string has to be done in scroll mode, as well es
26 displaying a warning/error if search is wrapped or nothing found.)
27 </p>
28
29 <p>
30 When the search command key ('/') was entered in the pager, display() quits
31 with RET_SEARCH. Additionally, "search.type" (see
32 <a href="#struct">Search Struct</a> below) is set to
33 SEARCH_FORWARD.
34 </p>
35
36 <p>
37 In <a href="hacking.html#main">main()</a> (see hacking.*), when
38 RET_SEARCH is encountered, first the search string is read from the user with
39 readline("/"). If '^D' was typed, the search is immediately aborted. If nothing
40 was typed in (just &lt;return>), we reuse the previous search string; otherwise we
41 store the new one.
42 </p>
43
44 <p>
45 Having this, the actual search is performed. This is described under
46 <a href="#search">Search</a> below.
47 </p>
48
49 <p>
50 The result of the search operation is a new cursor position. The main loop
51 iteration is ended now, and the pager gets restarted in the next iteration. The
52 display() then knows to jump to the new position by "search.type" being set.
53 </p>
54
55 </a> <!-- framework -->
56
57 <a name="struct" id="struct">
58
59 <h2>Search Struct</h2>
60
61 <p>
62 For passing information between the search code in the pager and in main(), as
63 well as between multiple searches, a global "search" struct is defined in
64 search.c.
65 </p>
66
67 <p>
68 This struct is of type "struct Search" and presently contains the following data:
69 <ul> <li>
70 "string" is the current/last search string requested. It is stored so it can
71 be reused when the user request search again (typing &lt;return> immediately at
72 the search prompt, see <a href="#framework">Framework</a> above.
73 </li><li>
74 "type" has a dual function: In the pager it is set so the search function in
75 main() will know what kind of search to perform: forward, backward, next...
76 (This is presently a no-op, as there is only one search type available...)
77 When returning to a pager the presence of this flag means there was a search
78 and the cursor needs to be set to the new position. Again, see
79 <a href="#framework">Framework</a> for details.
80 </li></ul>
81 </p>
82
83 </a> <!-- struct -->
84
85 <a name="search" id="search">
86
87 <h2>Search</h2>
88
89 <p>
90 The search itself is done in several steps. First we need to determine where on
91 the page the cursor stands to know where to search from, i.e. find out in which
92 text item, and the exact position inside this item's text string.
93 </p>
94
95 <p>
96 This part is fairly complicated, as there are several possibilities; it's
97 actually the most complicated part of all. The most basic possibility is that
98 the cursor stands inmidst some text line. For this to find out, we have to
99 check all text items present in the cursor line (using the
100 <a href="hacking-layout.html#pageMap">page_map[]</a>, which is described
101 under <a href="hacking-layout.html#createMap">create_map()</a> in
102 hacking-layout.*). For each of those items we look up the beginning and end of
103 the text line visible in the scanned page line using the helper functions from
104 <a href="hacking-layout.html#itemsC">items.c</a> (see
105 hacking-layout.*). Note that
106 <a href="hacking-layout.html#lineStartEnd">line_start() and
107 line_end()</a> return the position of the line inside the text string,
108 while <a href="hacking-layout.html#linePos">line_pos()</a> gives
109 the page position of the line start.
110 </p>
111
112 <p>
113 Now if the cursor actually stands inside the line (the offset of the cursor
114 position ralatively to the beginning of the line is >=0 and smaller than the
115 line width), we simply store the string position of the cursor, which is the
116 string position of the line start plus the offset.
117 </p>
118
119 <p><pre>
120 page:
121
122 First paragraph
123 with centered text. &lt;-- cursor_y
124 | ^
125 |&lt;------->|
126 line_pos() offset cursor_x
127
128 string: "First paragraph with centered text."
129 | ^
130 |&lt;------->|
131 line_start() offset start_pos
132 </pre></p>
133
134 <p>
135 The cursor may also stand before the beginning of the line. In this case we
136 want to search from the beginning of the line. This is achieved by just
137 assuming the cursor *does* stand at the beginning of the line (setting "offset"
138 to 0).
139 </p>
140
141 <p><pre>
142 First paragraph
143 with centered text. &lt;--
144 ^ |
145 |&lt;->|
146 offset&lt;0
147 </pre></p>
148
149 <p>
150 A third case is that the cursor stands behind the end of the text line, but
151 still inside the text block (i.e. this is not the last line). Here, the search
152 starts with the beginning of the next line. (Which is equal to the end of this
153 one.)
154 </p>
155
156 <p><pre>
157 line_start() line_end()
158 v v
159 First paragraph &lt;--
160 with centered text.
161 | ^
162 |&lt;--------------->|
163 offset >= line_end()-line_start()
164 </pre></p>
165
166 <p>
167 Another procedure is necessary if the cursor doesn't stand inside a text item
168 at all (the above search has no result). In this case we have to search from
169 the beginning of the next text item. For this, we simply scan all text items in
170 the page and take the first one that starts after "cursor_y". (Alternatively we
171 could scan the page linewise starting with the next line... This would be way
172 more efficient, but may cause problems when tables and similar things are
173 implemented. We will revise this at some point.)
174 </p>
175
176 <p><pre>
177 First paragraph &lt;-- item->y_start &lt;= cursor_y
178 with centered text.
179 &lt;-- cursor_y
180 Second paragraph. &lt;-- item->y_start > cursor_y &lt;== start_item
181 ^
182 start_pos=0
183 </pre></p>
184
185 <p>
186 Now the real search can start. It is done item by item, till the page end. In
187 each text item, we search for the search string inside the item's text string
188 with strstr(). For the first item, we start with "start_pos" as offset, so only
189 the string part after the cursor position is searched; for all following items,
190 "start_pos" is set to 0.
191 </p>
192
193 <p>
194 As soon as strstr() returns the first match, the matching item and the position
195 inside the string are memorized, and the search is terminated.
196 </p>
197
198 <p>
199 If nothing was found, the search is wrapped: In a second step, all items
200 beginning with the first one on the page and ending with the start item are
201 scanned. (Note that the start item is searched again, this time starting at the
202 beginning of the string. The part after "start_pos" is searched a second time,
203 but this shouldn't matter.)
204 </p>
205
206 <p>
207 There is an exception if the search started at the page end ("start_item" is
208 NULL): We can't scan up to the start item inclusive in this case, of course;
209 instead, we simply scan to the page end. (No special handling of this case is
210 necessary in the first pass, as that one just scans to the page end, thus will
211 simply terminate immediately.)
212 </p>
213
214 <p>
215 Finally the match position needs to be transformed back to page coordinates
216 again. This is much simpler than the other way round: We just need to find out
217 in which line of the text item the match position is located, and can calculate
218 y and x coordinates from the line number and the line position then.
219 </p>
220
221 <p><pre>
222 line_end(0) line_end(1)
223 v v
224 string: "First paragraph with centered text."
225 | ^
226 |&lt;----------->|
227 line_start(1) offset match_pos
228
229 page:
230
231 First paragraph
232 with centered text. &lt;-- cursor_y=line_end(1)
233 | ^
234 |&lt;----------->|
235 line_pos(1) offset cursor_x
236 </pre></p>
237
238 </a> <!-- search -->
239
240 </body>
241 </html>