Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 710 lines (622 sloc) 18.282 kb
8d1ac0c1 »
2011-12-10 Import Elvis 2.1 (written by Steve Kirkendall)
1 /* tagsrch.c */
2
3 /* Elvis uses this file to scan a tags file, and built a list of the matching
4 * tags, sorted by name and likelyhood that they're the intended tag.
5 *
6 * Entry points are:
7 * void tsreset() forget old restrictions
8 * void tsparse(text) add new restrictions
9 * void tsadjust(tag, oper) adjust likelyhood heuristic data
10 * void tsfile(filename) scan a file for tags, add to taglist
11 */
12
13 #include "elvis.h"
14
15 #define WEIGHT_SUCCESS 100
16 #define WEIGHT_FAIL 95
17 #define WEIGHT_AGING 10
18
19 /* These structures are used for storing a list of acceptable values for a
20 * particular attribute.
21 */
22 typedef struct value_s
23 {
24 struct value_s *next; /* another possible value */
25 char *value; /* attribute's possible value */
26 } value_t;
27
28
29 /* These structures are used for storing a list of restrictive names, and
30 * their possible values.
31 */
32 typedef struct name_s
33 {
34 struct name_s *next; /* another restriction */
35 char *name; /* attribute's name */
36 long weight; /* 1=required, 0=optional */
37 value_t *values; /* list of possible values */
38 } name_t;
39
40
41 #if USE_PROTOTYPES
42 static name_t *addrestrict(char *nametext, char *valuetext, _char_ oper);
43 static long likelyhood(TAG *tag, name_t *head, name_t *map[]);
44 static name_t *age(name_t *head);
45 static BOOLEAN chkrestrict(TAG *tag);
46
47 #endif /* USE PROTOTYPES */
48
49 /* These are the heads of a three of lists: one for restrictions, one for
50 * attributes of recent successful searches, and one for attributes of recent
51 * failed searches. Also, there are map tables that allow a given name to be
52 * found quickly via its attribute index in the current tags file.
53 */
54 static name_t *rhead, *rmap[MAXATTR]; /* restrictions */
55 static name_t *shead, *smap[MAXATTR]; /* attributes from succeeded searches */
56 static name_t *fhead, *fmap[MAXATTR]; /* attributes from failed searches */
57 static int nmandatory; /* number of mandatory restrictions */
58 #define NO_NAME (((name_t *)0) + 1)
59
60
61 /* These store the first and last tagnames that we care about, sorted in
62 * ASCII order like the tags file. This helps us quickly skip tags that we
63 * don't care about. If there is no tagname restriction, these are NULL.
64 * The longname option stores the length of the longest name.
65 */
66 static char *firstname, *lastname;
67 static int longname;
68 static int taglength;
69 static BOOLEAN fulllength;
70
71
72 /* This function adds a name/value pair to the list of restrictions, and
73 * returns a pointer to the name_t record. It chooses which list to update
74 * based on the operator.
75 */
76 static name_t *addrestrict(nametext, valuetext, oper)
77 char *nametext; /* text form of restrictive name */
78 char *valuetext; /* text form of possible value, or NULL */
79 _char_ oper; /* one of {= : + -} from command line */
80 {
81 name_t **list; /* the list to search */
82 name_t *name, *namelag;/* for scanning the names list */
83 value_t *value, *vlag; /* for scanning the values list */
84 long i;
85 int len;
86
87 /* choose a list */
88 switch (oper)
89 {
90 case '+': list = &shead; break; /* the succeeded attributes */
91 case '-': list = &fhead; break; /* the failed attributed */
92 default: list = &rhead; /* the restrictions */
93 }
94
95 /* search for the name in the list. Add it if new */
96 for (namelag = NULL, name = *list;
97 name && strcmp(nametext, name->name);
98 namelag = name, name = name->next)
99 {
100 }
101 if (!name)
102 {
103 name = (name_t *)safealloc(1, sizeof(name_t));
104 name->name = safedup(nametext);
105 name->weight = 0;
106 if (namelag)
107 namelag->next = name;
108 else
109 *list = name;
110 }
111
112 /* insert the value into the list of acceptable values */
113 if (valuetext)
114 {
115 value = (value_t *)safealloc(1, sizeof(value_t));
116 value->value = safedup(valuetext);
117 value->next = name->values;
118 name->values = value;
119 }
120
121 /* adjust the weight */
122 switch (oper)
123 {
124 case '+':
125 case '-':
126 if (valuetext)
127 {
128 name->weight = (oper == '+') ? WEIGHT_SUCCESS : WEIGHT_FAIL;
129 }
130
131 /* discard any older values which have no weight */
132 for (i = name->weight, vlag = NULL, value = name->values;
133 i > 0 && value;
134 i -= WEIGHT_AGING, vlag = value, value = value->next)
135 {
136 }
137 if (vlag)
138 vlag->next = NULL;
139 else
140 name->values = NULL;
141 while (value)
142 {
143 vlag = value->next;
144 safefree(value->value);
145 safefree(value);
146 value = vlag;
147 }
148 break;
149
150 case ':':
151 name->weight = 0; /* optional */
152 break;
153
154 case '/':
155 name->weight = 2; /* optional, but counts against mandatory */
156 break;
157
158 case '=':
159 name->weight = 1; /* required */
160 for (nmandatory = 0, namelag = rhead;
161 namelag;
162 namelag = namelag->next)
163 {
164 if (namelag->weight == 1)
165 nmandatory++;
166 }
167 break;
168 }
169
170 /* if adding to the tagname attribute, then update firstname and
171 * lastname variables.
172 */
173 if (!strcmp(name->name, "tagname"))
174 {
175 firstname = lastname = NULL;
176 longname = 0;
177 for (value = name->values; value; value = value->next)
178 {
179 if (!firstname || strcmp(firstname, value->value) > 0)
180 firstname = value->value;
181 if (!lastname || strcmp(lastname, value->value) < 0)
182 lastname = value->value;
183 len = strlen(value->value);
184 if (len > longname)
185 longname = len;
186 }
187 }
188
189 /* return the name_t record of this item */
190 return name;
191 }
192
193
194 /* Assign a likelyhood value to a tag, by comparing its attributes to those
195 * of recent successful or failed tag searches. The tag's total weight can
196 * be computed by taking the likelyhood of success minus the likelyhood of
197 * failure.
198 *
199 * In addition to returning the partial likelyhood, this function also updates
200 * the smap[] or fmap[] array.
201 */
202 static long likelyhood(tag, head, map)
203 TAG *tag; /* a tag to check */
204 name_t *head; /* either shead or fhead */
205 name_t *map[]; /* either smap[] or fmap[] */
206 {
207 long weight, total;
208 name_t *name;
209 value_t *value;
210 int i;
211
212 /* for all attributes including the standard ones... */
213 total = 0;
214 for (i = 0; i < MAXATTR && tagattrname[i]; i++)
215 {
216 /* if this tag lacks this attribute, skip it */
217 if (!tag->attr[i])
218 continue;
219
220 /* locate the name_t record */
221 if (map[i])
222 name = map[i];
223 else
224 {
225 for (name = head;
226 name && strcmp(name->name, tagattrname[i]);
227 name = name->next)
228 {
229 }
230 if (!name)
231 {
232 name = NO_NAME;
233 }
234 map[i] = name;
235 }
236
237 /* if there is no name_t record, ignore this attribute */
238 if (name == NO_NAME)
239 {
240 continue;
241 }
242
243 /* try to find the tag's value in recent values */
244 for (weight = name->weight, value = name->values;
245 value && *value->value && strcmp(value->value, tag->attr[i]);
246 weight -= WEIGHT_AGING, value = value->next)
247 {
248 }
249 if (value)
250 {
251 total += weight;
252 }
253 }
254
255 /* return the total weight (for either success or failure) */
256 return total;
257 }
258
259
260 /* Age the successful/failed tag search data. This will eventually cause old
261 * data to be freed. Returns the new head of the list. Doesn't depend on or
262 * update smap[] or fmap[].
263 */
264 static name_t *age(head)
265 name_t *head; /* either shead or fhead */
266 {
267 name_t *scan, *lag;
268 value_t *value, *vlag;
269 long weight;
270
271 /* for each named attribute... */
272 for (scan = head, lag = NULL; scan; lag = scan, scan = scan->next)
273 {
274 /* decrement its weight */
275 scan->weight -= WEIGHT_AGING;
276
277 /* free any older values which would have zero weight */
278 for (weight = scan->weight, value = scan->values, vlag = NULL;
279 value && weight > 0;
280 weight--, vlag = value, value = value->next)
281 {
282 }
283 if (vlag)
284 vlag->next = NULL;
285 else
286 scan->values = NULL;
287 while (value)
288 {
289 vlag = value->next;
290 safefree(value->value);
291 safefree(value);
292 value = vlag;
293 }
294
295 /* if this name has no values left, then delete it */
296 if (!scan->values)
297 {
298 if (lag)
299 lag->next = scan->next;
300 else
301 head = scan->next;
302 safefree(scan->name);
303 safefree(scan);
304 if (lag)
305 scan = lag;
306 else if (head)
307 scan = head;
308 else
309 break;
310 }
311 }
312
313 /* return the new head */
314 return head;
315 }
316
317
318
319 /* This function wipes out the restrictions list. The succeeded and failed
320 * attribute lists are unaffected.
321 */
322 void tsreset P_((void))
323 {
324 name_t *nextname;
325 value_t *nextvalue;
326
327 /* for each name... */
328 while (rhead)
329 {
330 /* for each value */
331 while (rhead->values)
332 {
333 /* free the value */
334 nextvalue = rhead->values->next;
335 safefree(rhead->values->value);
336 safefree(rhead->values);
337 rhead->values = nextvalue;
338 }
339
340 /* free the name */
341 nextname = rhead->next;
342 safefree(rhead->name);
343 safefree(rhead);
344 rhead = nextname;
345 }
346
347 /* clobber the rmap[] array, too */
348 memset(rmap, 0, sizeof rmap);
349
350 /* clobber the firstname and lastname variables */
351 firstname = lastname = NULL;
352 longname = 0;
353
354 /* clobber the nmandatory variable */
355 nmandatory = 0;
356 }
357
358
359 /* This function parses a restrictions command line. The command line may have
360 * any number of restrictions. You can call this function repeatedly to combine
361 * multiple restrictions lines; You will usually call tsreset() before the first
362 * tsparse().
363 *
364 * A typical input: tsparse("mytag class:=DbItem,DbCustomer file:+myfile.cpp")
365 *
366 * Supported operators are:
367 * name:value Add a value for an optional attribute
368 * name:=value Add a value for a mandatory attribute
369 * name:/value Add a value for an optional attribute, but require the
370 * value to be a substring of the tagaddress value
371 * name:+value Pretend name:value was part of a recent successful tag
372 * name:-value Pretend name:value was part of a recent failed tag
373 * Also, a ',' character can be used to repeat the prevous operator; e.g.,
374 * "class:/DbItem,DbCust", "class:/DbItem:/DbCust" are both identical in effect
375 * to "class:/DbItem class:/DbCustomer".
376 *
377 * THE TEXT IS CLOBBERED!
378 */
379 void tsparse(text)
380 char *text; /* a "name:value name:value" string. */
381 {
382 char *name; /* start of a name within the text */
383 char *value; /* start of a value within the text */
384 char *copy; /* used while deleting backslashes */
385 char oper; /* most recent operator character */
386 char nextoper; /* operator for the next value */
387
388 /* for each word (delimited by whitespace or an operator) ... */
389 for (name = NULL, nextoper = oper = ' '; text && *text; oper = nextoper)
390 {
391 /* skip redundant whitespace */
392 while (*text == ' ' || *text == '\t')
393 {
394 text++;
395 }
396 if (!*text) break;
397
398 /* value (or maybe name?) starts here */
399 value = text;
400
401 /* skip over characters of value */
402 for (copy = text; *text && !strchr(":, \t", *text); )
403 {
404 if (*text == '\\' && text[1])
405 text++;
406 *copy++ = *text++;
407 }
408
409 /* Get the NEXT operator and mark the end of the name. ',' is
410 * treated as a repeat of previous.
411 */
412 if (*text != ',')
413 nextoper = *text;
414 if (*text)
415 *text++ = '\0';
416 *copy = '\0';
417 if (!nextoper || nextoper == '\t')
418 nextoper = ' ';
419 if (nextoper == ':' && *text && strchr("=+-/", *text))
420 nextoper = *text++;
421
422 /* Use THIS operator to decide how to handle this value */
423 switch (oper)
424 {
425 case ' ': /* value or name<nextoper>... */
426 /* Two possible cases: If the NEXT operator is
427 * whitespace then this value is assumed to be the
428 * value of the "tagname" attribute. Otherwise, this
429 * value is actually an attribute name which will be
430 * used for later values (up to the next whitespace)
431 */
432 if (nextoper == ' ')
433 (void)addrestrict("tagname", value, '=');
434 else if (!*text)
435 (void)addrestrict(value, "", nextoper);
436 else
437 name = value;
438 break;
439
440 case '/': /* name:/value */
441 /* use this value with the previously mentioned name */
442 (void)addrestrict(name, value, '/');
443
444 /* also use as a mandatory address substring */
445 (void)addrestrict("tagaddress", value, '=');
446 break;
447
448 default: /* name:value name:=value name:+value name:-value */
449 /* use this value with the previously mentioned name */
450 (void)addrestrict(name, value, oper);
451 }
452 }
453 }
454
455
456 /* Check a given tag against the restrictions. Return True if it satisfies. */
457 static BOOLEAN chkrestrict(tag)
458 TAG *tag;
459 {
460 int mandcnt;/* number of mandatory restrictions which matched */
461 name_t *name; /* a "name" struct for a restriction */
462 value_t *value; /* a "value" struct from within "name"'s list */
463 char *scan;
464 int i;
465
466 /* for each attribute... */
467 for (i = mandcnt = 0; i < MAXATTR && tagattrname[i]; i++)
468 {
469 /* locate the name_t for this attribute. If there is none,
470 * then ignore this attribute.
471 */
472 if (rmap[i] == NO_NAME)
473 continue;
474 else if (rmap[i])
475 name = rmap[i];
476 else
477 {
478 for (name = rhead;
479 name && strcmp(name->name, tagattrname[i]);
480 name = name->next)
481 {
482 }
483 if (!name)
484 {
485 rmap[i] = NO_NAME;
486 continue;
487 }
488 rmap[i] = name;
489 }
490
491 /* skip the TAGADDR attribute until later */
492 if (&tag->attr[i] == &tag->TAGADDR)
493 continue;
494
495 /* if required and tag doesn't have it, then reject */
496 if (tag->attr[i])
497 mandcnt += name->weight;
498 else if (name->weight == 1)
499 return False;
500
501 /* if optional and tag doesn't have it, ignore it */
502 if (!tag->attr[i])
503 continue;
504
505 /* check against all acceptable values */
506 if (fulllength || tag->attr[i] != tag->TAGNAME)
507 {
508 for (value = name->values;
509 value && *value->value && strcmp(value->value, tag->attr[i]);
510 value = value->next)
511 {
512 }
513 }
514 else
515 {
516 for (value = name->values;
517 value && strncmp(value->value, tag->attr[i], (int)taglength);
518 value = value->next)
519 {
520 }
521 }
522 if (!value)
523 return False;
524 }
525
526 /* As a special case, if there are tagaddress restrictions, then the
527 * tag's address field must contain one of them as a substring.
528 */
529 name = rmap[2];
530 if (name != NO_NAME && name && name->values && mandcnt < nmandatory)
531 {
532 /* for each possible address substring... */
533 for (value = name->values; value; value = value->next)
534 {
535 /* search for the substring within the tag's address */
536 i = strlen(value->value);
537 if ((int)strlen(tag->TAGADDR) <= i + 2)
538 continue;
539 for (scan = tag->TAGADDR + 1;
540 scan[i] &&
541 (isalnum(scan[-1])
542 || isalnum(scan[i])
543 || *scan != *value->value
544 || strncmp(scan, value->value, i));
545 scan++)
546 {
547 }
548
549 /* if found, then stop looking */
550 if (scan[i])
551 break;
552 }
553
554 /* if no substring was found, then reject */
555 if (!value)
556 return False;
557
558 /* If mandatory, count it */
559 if (name->weight > 0)
560 mandcnt++;
561 }
562
563 /* if some mandatory values were missing, reject it */
564 if (mandcnt < nmandatory)
565 return False;
566
567 /* if nothing wrong with it, then it is acceptable */
568 return True;
569 }
570
571
572
573
574 /* Adjust the histories of failed or successful searches. Returns the head of
575 * the list. Doesn't depend on or update smap[] or fmap[].
576 */
577 void tsadjust(tag, oper)
578 TAG *tag; /* a tag that recently succeeded or failed */
579 _char_ oper; /* '+' if succeeded, '-' if failed */
580 {
581 int i;
582
583 /* age both histories */
584 shead = age(shead);
585 fhead = age(fhead);
586
587 /* for each attribute, except the standard ones... */
588 for (i = 3; i < MAXATTR && tagattrname[i]; i++)
589 {
590 /* if this tag had such an attribute... */
591 if (tag->attr[i])
592 {
593 /* add it to the history */
594 addrestrict(tagattrname[i], tag->attr[i], oper);
595 }
596 }
597 }
598
599
600 /* Scan a file for tags which meet the restrictions, and add them to the list */
601 void tsfile(filename, maxlength)
602 char *filename; /* name of a file to scan */
603 long maxlength; /* maximum significant length, or 0 for all */
604 {
605 CHAR tagline[1000]; /* input buffer */
606 BOOLEAN allnext; /* does tagline[] contain the whole next line?*/
607 int bytes; /* number of bytes in tagline */
608 CHAR *src, *dst; /* for manipulating tagline[] */
609 TAG *tag; /* a tag parsed from tagline[] */
610 int i;
611
612 /* clobber the rmap[], smap[], and fmap[] arrays */
613 memset(rmap, 0, sizeof rmap);
614 memset(smap, 0, sizeof smap);
615 memset(fmap, 0, sizeof fmap);
616
617 /* clobber the attribute names */
618 tagnamereset();
619
620 /* choose a significant length */
621 if (maxlength == 0 || maxlength > longname)
622 taglength = longname, fulllength = True;
623 else
624 taglength = maxlength, fulllength = False;
625
626 /* open the file */
627 if (!ioopen(filename, 'r', True, False, 't'))
628 {
629 return;
630 }
631
632 /* Make a local copy of the filename. This is important because the
633 * value passed into this function is usually the static buffer used
634 * by the dirpath() function, and we want to use that buffer ourselves
635 * later in this function.
636 */
637 filename = safedup(filename);
638
639 /* Compare the tag of each line against the tagname */
640 bytes = ioread(tagline, QTY(tagline) - 1);
641 while (bytes > taglength
642 && (!lastname || CHARncmp(lastname, tagline, (size_t)taglength) >= 0))
643 {
644 /* disable firstname/lastname checks if tags file claims to
645 * be unsorted.
646 */
647 if (lastname && *tagline == '!' && !CHARncmp(tagline, toCHAR("!_TAG_FILE_SORTED\t0\t"), 20))
648 lastname = firstname = NULL;
649
650 /* find the end of this line */
651 for (src = tagline; src < &tagline[bytes] && *src != '\n'; src++)
652 {
653 }
654 *src = '\0';
655
656 /* if not obviously too early to be of interest, parse it and
657 * process it...
658 */
659 if ((!firstname || CHARncmp(firstname, tagline, taglength) <= 0)
660 && (tag = tagparse(tochar8(tagline))) != NULL)
661 {
662 /* do we want to keep this tag? */
663 if (*filename == '!')
664 {
665 /* Yes! compute its likelyhood factor */
666 tag->match = likelyhood(tag, shead, smap)
667 - likelyhood(tag, fhead, fmap);
668 for (i = 3; i < MAXATTR; i++)
669 if (tag->attr[i])
670 tag->match++;
671
672 /* save a copy of it */
673 (void)tagadd(tagdup(tag));
674 }
675 else if (chkrestrict(tag))
676 {
677 /* Yes! compute its likelyhood factor */
678 tag->match = likelyhood(tag, shead, smap)
679 - likelyhood(tag, fhead, fmap);
680 for (i = 3; i < MAXATTR; i++)
681 if (tag->attr[i])
682 tag->match++;
683
684 /* replace the filename with full pathname */
685 tag->TAGFILE = dirpath(dirdir(filename), tag->TAGFILE);
686 /* save a copy of it */
687 (void)tagadd(tagdup(tag));
688 }
689 }
690
691 /* delete this line from tagline[] */
692 for (dst = tagline, src++, allnext = False; src < &tagline[bytes]; )
693 {
694 if (*src == '\n')
695 allnext = True;
696 *dst++ = *src++;
697 }
698 bytes = (int)(dst - tagline);
699
700 /* if the next line is incomplete, read some more text
701 * from the tags file.
702 */
703 if (!allnext || bytes <= taglength)
704 {
705 bytes += ioread(dst, (int)QTY(tagline) - bytes - 1);
706 }
707 }
708 safefree(filename);
709 (void)ioclose();
710 }
Something went wrong with that request. Please try again.