>Number:         22736
>Category:       bin
>Synopsis:       vi can't handle unsorted tags files
>Confidential:   no
>Severity:       non-critical
>Priority:       medium
>Responsible:    bin-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Tue Sep 09 20:41:00 UTC 2003
>Closed-Date:
>Last-Modified:
>Originator:     Eric Haszlakiewicz
>Release:        NetBSD 1.6W
>Organization:
>Environment:
System: NetBSD jodi.nimenees.com 1.6W NetBSD 1.6W (JODI) #0: Tue Aug 5 13:29:36 CDT 2003 root@poe.nimenees.com:/usr/build/JODI i386
Architecture: i386
Machine: i386
>Description:
	vi can't handle tags file that don't have all the lines in sorted
order.  These are easily created with ctags -a.
>How-To-Repeat:
	cd /usr/src/sys ; find . -name \*.c | xargs ctags -a
	vi -t bdevsw_lookup
>Fix:
	Use this patch, which does a full scan through the tags file(s) if the
quick binary search doesn't work.

Index: ex_tag.c
===================================================================
RCS file: /cvsroot/src/usr.bin/vi/ex/ex_tag.c,v
retrieving revision 1.13
diff -u -d -r1.13 ex_tag.c
--- ex_tag.c	2002/04/09 01:47:34	1.13
+++ ex_tag.c	2003/09/09 20:39:35
@@ -57,9 +57,10 @@
 static int	 getentry __P((char *, char **, char **, char **));
 static TAGQ	*gtag_slist __P((SCR *, char *, int));
 #endif
-static int	 ctag_sfile __P((SCR *, TAGF *, TAGQ *, char *));
+static int	 ctag_sfile __P((SCR *, TAGF *, TAGQ *, char *, int));
 static TAGQ	*ctag_slist __P((SCR *, char *));
 static char	*linear_search __P((char *, char *, char *));
+static char	*full_search __P((char *, char *, char *));
 static int	 tag_copy __P((SCR *, TAG *, TAG **));
 static int	 tag_pop __P((SCR *, TAGQ *, int));
 static int	 tagf_copy __P((SCR *, TAGF *, TAGF **));
@@ -1144,6 +1145,7 @@
 	TAGQ *tqp;
 	size_t len;
 	int echk;
+	int slow_search = 0;
 
 	exp = EXP(sp);
 
@@ -1158,16 +1160,21 @@
 	 * Find the tag, only display missing file messages once, and
 	 * then only if we didn't find the tag.
 	 */
-	for (echk = 0,
-	    tfp = exp->tagfq.tqh_first; tfp != NULL; tfp = tfp->q.tqe_next)
-		if (ctag_sfile(sp, tfp, tqp, tag)) {
-			echk = 1;
-			F_SET(tfp, TAGF_ERR);
-		} else
-			F_CLR(tfp, TAGF_ERR | TAGF_ERR_WARN);
+	do {
+		for (echk = 0,
+			tfp = exp->tagfq.tqh_first; tfp != NULL; tfp = tfp->q.tqe_next)
+			if (ctag_sfile(sp, tfp, tqp, tag, slow_search)) {
+				echk = 1;
+				F_SET(tfp, TAGF_ERR);
+			} else
+				F_CLR(tfp, TAGF_ERR | TAGF_ERR_WARN);
+			if (slow_search)
+				break;
+			slow_search = 1;
+	} while (CIRCLEQ_EMPTY(&tqp->tagq));
 
 	/* Check to see if we found anything. */
-	if (tqp->tagq.cqh_first == (void *)&tqp->tagq) {
+	if (CIRCLEQ_EMPTY(&tqp->tagq)) {
 		msgq_str(sp, M_ERR, tag, "162|%s: tag not found");
 		if (echk)
 			for (tfp = exp->tagfq.tqh_first;
@@ -1194,11 +1201,12 @@
  *	Search a tags file for a tag, adding any found to the tag queue.
  */
 static int
-ctag_sfile(sp, tfp, tqp, tname)
+ctag_sfile(sp, tfp, tqp, tname, slow_search)
 	SCR *sp;
 	TAGF *tfp;
 	TAGQ *tqp;
 	char *tname;
+	int slow_search;
 {
 	struct stat sb;
 	TAG *tp;
@@ -1237,8 +1245,13 @@
 
 	front = map;
 	back = front + sb.st_size;
-	front = binary_search(tname, front, back);
-	front = linear_search(tname, front, back);
+	if (slow_search)
+		front = full_search(tname, map, back);
+	else
+	{
+		front = binary_search(tname, front, back);
+		front = linear_search(tname, front, back);
+	}
 	if (front == NULL)
 		goto done;
 
@@ -1438,8 +1451,9 @@
  *
  * This routine assumes:
  *
- * 	o front points at the first character in a line.
- *	o front is before or at the first line to be printed.
+ *  o front points at the first character in a line.
+ *  o front is before or at the first line to be printed.
+ *  o the lines are sorted.
  */
 static char *
 linear_search(string, front, back)
@@ -1453,6 +1467,31 @@
 			return (NULL);
 		case GREATER:		/* Keep going. */
 			break;
+		}
+		SKIP_PAST_NEWLINE(front, back);
+	}
+	return (NULL);
+}
+
+/*
+ * Find the first line that starts with string, linearly searching from front
+ * to back.
+ *
+ * Return NULL for no such line.
+ *
+ * This routine assumes:
+ *
+ *  o front points at the first character in a line.
+ *  o front is before or at the first line to be printed.
+ */
+static char *
+full_search(string, front, back)
+	char *string, *front, *back;
+{
+	while (front < back) {
+		if (compare(string, front, back) == EQUAL)
+		{
+			return (front);
 		}
 		SKIP_PAST_NEWLINE(front, back);
 	}
>Release-Note:
>Audit-Trail:
>Unformatted: