WALLACE, Circuit Judge:
Schwartzmiller filed a petition for writ of habeas corpus, challenging his conviction and confinement on three counts under Idaho Code § 18-6607 (1979) (now amended by Idaho Code § 18-1508 (Supp.1984)), for performing lewd and lascivious acts on a child, on the ground that the statute is unconstitutionally vague. The district court declared the statute to be unconstitutionally vague on its face, but not as applied to some but not all of Schwartzmiller’s conduct. Schwartzmiller v. Gardner, 567 F.Supp. 1371, 1376-79 (D.Idaho 1983). Schwartzmiller appeals the district court’s denial of his petition, and the state cross-appeals the court’s ruling that the statute is void for vagueness on its face and void as applied to part of Schwartzmiller’s conduct. The district court exercised jurisdiction under 28 U.S.C. § 2241(a), and we have jurisdiction under 28 U.S.C. § 2253. The issues in this case are all questions of law, reviewable de novo. United States v. McConney, 728 F.2d 1195, 1201 (9th Cir.) (en banc), cert. denied, — U.S. —, 105 S.Ct. 101, 83 L.Ed.2d 46 (1984). We affirm in part and reverse in part.
I
Schwartzmiller, an Idaho state prisoner, was convicted in 1977 pursuant to Idaho Code § 18-6607 for performing lewd and lascivious acts on a child. The Idaho Supreme Court reversed his conviction on the basis of procedural error and ordered a new trial, without deciding his claim that the statute was unconstitutionally vague. Schwartzmiller v. Winters, 99 Idaho 18, 576 P.2d 1052 (1978). He was never retried on this charge. Schwartzmiller v. Gardner, 567 F.Supp. at 1375.
In 1981, Schwartzmiller again was convicted under section 18-6607, based on incidents distinct from those forming the basis of his 1977 conviction. While his state appeal on this second conviction was pending, he filed a petition for writ of habeas corpus, challenging section 18-6607 as unconstitutionally vague and therefore void. The district court dismissed his petition for [1344]*1344failure to exhaust state remedies. In an unpublished disposition, we reversed, ordering the district court to consider the merits of the habeas corpus petition. Schwartzmiller v. Gardner, 692 F.2d 765 (9th Cir.1982) (mem.).
On remand, the district court held that, notwithstanding various Idaho decisions applying and attempting to explain and narrow section 18-6607, Schwartzmiller v. Gardner, 567 F.Supp. at 1374-76, the statute “is unconstitutionally vague on its face.” Id. at 1382. Paradoxically, the court also held that because the Idaho Supreme Court had previously indicated that the “commission of an infamous crime against nature on a minor child will render the perpetrator subject to the provisions of § 18-6607,” id. at 1377, citing State v. Wall, 73 Idaho 142, 144, 248 P.2d 222, 223 (1952), and because the United States Supreme Court had upheld “a statute proscribing ‘crimes against nature’ ” against a vagueness attack, id. at 1378, citing Rose v. Locke, 423 U.S. 48, 53, 96 S.Ct. 243, 246, 46 L.Ed.2d 185 (1975) (Brennan, J., dissenting) (arguing that at common law crime against nature referred only to anal intercourse and not to sodomy in general), section 18-6607 was not unconstitutionally vague as applied to Schwartzmiller’s convictions on two counts of performing anal intercourse on one of two fourteen-year old boys. Id. at 1377-78. The district court did find the statute unconstitutionally vague as applied to his conviction on a third count for masturbating the other fourteen-year old boy. Although that count also contained a charge of attempted anal intercourse with the boy, the court could not ascertain whether the jury relied on the masturbation charge, and thus held the conviction on that count violative of due process. Id. at 1378. The court decided that this ruling afforded no immediate relief, however, because the sentence for the third count would not begin until the sentences for the first two anal intercourse counts had been served. Id. at 1378-79. The court refused to disturb the jury’s finding that SchwartzmiUer engaged in his acts with the specific intent to arouse sexual passions required by section 18-6607. Id. at 1379-80.
After the district court issued its decision, the Idaho Supreme Court heard Schwartzmiller’s appeal of his 1981 conviction. It rejected his claims that section 18-6607 is unconstitutionally vague, or that he was unfairly deprived of the opportunity to cross-examine the boys. State v. Schwartzmiller, 107 Idaho 89, 685 P.2d 830 (1984).
II
The state challenges Schwartzmiller’s habeas corpus petition on the ground that his present incarceration relates solely to his 1981 conviction, and not his 1977 conviction, and thus he had not exhausted his state remedies by the time he filed this petition. Ordinarily, a state prisoner may not obtain federal habeas corpus relief without first exhausting all state remedies available at the time he files for relief. See Rose v. Lundy, 455 U.S. 509, 515-20, 102 S.Ct. 1198, 1201-04, 71 L.Ed.2d 379 (1982); Humphrey v. Cady, 405 U.S. 504, 516, 92 S.Ct. 1048, 1055, 31 L.Ed.2d 394 (1972), citing Fay v. Noia, 372 U.S. 391, 434-35, 83 S.Ct. 822, 846-47, 9 L.Ed.2d 837 (1963). The exhaustion requirement as to a particular claim is satisfied once the claim has been fairly presented to the highest court of the state. See Jackson v. Cupp, 693 F.2d 867, 869 (9th Cir.1982). See also Pi-card v. Connor, 404 U.S. 270, 275, 92 S.Ct. 509, 512, 30 L.Ed.2d 438 (1971); Hudson v. Rushen, 686 F.2d 826, 830 (9th Cir.1982), cert. denied, 461 U.S. 916, 103 S.Ct. 1896, 77 L.Ed.2d 285 (1983). The exhaustion doctrine, however, is not jurisdictional, but reflects a policy of federal-state comity. Rose v. Lundy, 455 U.S. at 515-16, 102 S.Ct. at 1201-02; Picard v. Connor, 404 U.S. at 275, 92 S.Ct. at 512. Thus, an appellate court may give relief if state remedies are exhausted by the time it acts, even if these remedies were not exhausted when the habeas corpus petition was filed. See Sharpe v. Buchanan, 317 U.S. 238, 63 S.Ct. 245, 87 L.Ed. 238 (1942) (per curiam); Thomas v. Teets, 205 F.2d 236, 240-41 (9th [1345]*1345Cir.), cert. denied, 346 U.S. 910, 74 S.Ct. 240, 98 L.Ed. 407 (1953).
Because of this, we need not decide whether Schwartzmiller had exhausted his state remedies at the time he filed this habeas corpus petition, or whether, in light of our earlier unpublished decision, the law of the case doctrine prevents us from reexamining the exhaustion issue. After Schwartzmiller filed his habeas corpus petition, the Idaho Supreme Court heard his challenge to section 18-6607 on the appeal from his 1981 conviction. We conclude that, for purposes of this appeal, the exhaustion requirement has been satisfied.
Ill
Schwartzmiller challenges the state’s standing to appeal. He asserts that the state was the “all-prevailing” party in the district court’s decision, and thus may not cross-appeal from what he characterizes as the district court’s “dictum” that section 18-6607 is void for vagueness on its face and void as applied to his masturbation conviction.
The state may appeal both rulings; they are not irrelevant dictum. Parties may appeal any adverse finding that “form[s] the basis for collateral estoppel in subsequent litigation.” 9 J. Moore, Moore’s Federal Practice ¶ 203.06, at 3-24 (2d ed. 1983). See also Partmar Corp. v. Paramount Pictures Theatres Corp., 347 U.S. 89, 99 n. 6, 74 S.Ct. 414, 420 n. 6, 98 L.Ed. 532 (1954); Electrical Fittings Corp. v. Thomas & Betts Co., 307 U.S. 241, 242, 59 S.Ct. 860, 83 L.Ed. 1263 (1939). Because the district court’s conclusion that section 18-6607 is unconstitutionally vague as applied to masturbation would bind the state in subsequent litigation, the state has standing to appeal the ruling.
The state also has standing to appeal on the ground that parties may appeal a ruling which creates a “risk that they might become aggrieved upon reversal on the direct appeal.” Hilton v. Mumaw, 522 F.2d 588, 603 (9th Cir.1975). If the district court’s statement that section 18-6607 “is unconstitutionally vague on its face” were merely dictum or a description of the statute’s language standing alone, the state might face little or no risk of becoming aggrieved. But the statement is a separate holding. A complete “facial” vagueness analysis consists of examining statutory language as narrowed by state decisions, Wainwright v. Stone, 414 U.S. 21, 23, 94 S.Ct. 190, 192, 38 L.Ed.2d 179 (1973) (per curiam), and declaring the narrowed statute void for vagueness on its face. This is precisely what the district court did before proceeding to an “as applied” analysis. See 567 F.Supp. at 1372-78. Thus, rather than being merely dictum or a description of the statute’s bare language, the district court’s “facial” analysis is a separate holding. Because the state risks having this “facial” ruling take effect should the district court’s “as applied” holding be reversed, it may appeal the “facial” conclusion.
IV
We now reach the heart of this appeal, which is whether the district court correctly applied the void for vagueness doctrine. This doctrine is an aspect of due process and requires that the meaning of a penal statute be determinable. A statute is void for vagueness if it fails to give adequate notice to people of ordinary intelligence concerning the conduct it proscribes, see Coates v. City of Cincinnati, 402 U.S. 611, 614, 91 S.Ct. 1686, 1688, 29 L.Ed.2d 214 (1971) (Coates), or if it invites arbitrary and discriminatory enforcement, Papachristou v. City of Jacksonville, 405 U.S. 156, 162, 92 S.Ct. 839, 843, 31 L.Ed.2d 110 (1972). See also Jordan v. De George, 341 U.S. 223, 231-32, 71 S.Ct. 703, 707-08, 95 L.Ed. 886 (1951). Neither of these strands may be applied mechanically, however, but by a reasoning process. This follows because potential criminals do not necessarily learn what is forbidden by reading a statute’s literal language or cases construing the statutory language and because, although “[a] vague statute may invite arbitrary enforcement, ... virtually [1346]*1346any law allows it.” P. Low, J. Jeffries & R. Bonnie, Criminal Law 68-69 (1982) (emphasis in original). Judgment is necessary to determine “[t]he degree of vagueness that the Constitution tolerates — as well as the relative importance of fair notice and fair enforcement” and this, in turn, “depends in part on the nature of the enactment.” Village of Hoffman Estates v. The Flipside, Hoffman Estates, Inc., 455 U.S. 489, 498, 102 S.Ct. 1186, 1193, 71 L.Ed.2d 362 (1982) (Flipside)] see also United States v. Petrillo, 332 U.S. 1, 7-8, 67 S.Ct. 1538, 1541-42, 91 L.Ed. 1877 (1947) (“[T]he Constitution does not require impossible standards.”).
Related to, but distinct from, the vagueness doctrine is the doctrine of over-breadth. See Kolender v. Lawson, 461 U.S. 352, 103 S.Ct. 1855, 1859 n. 8, 75 L.Ed.2d 903 (1983) (Kolender); Zwickler v. Koota, 389 U.S. 241, 249-50, 88 S.Ct. 391, 396, 19 L.Ed.2d 444 (1967); G. Gunther, Constitutional Law 1188 n. 9 (10th ed. 1980). A law is overbroad if it prohibits not only acts the legislature may forbid, but also constitutionally protected conduct.
A.
The vagueness doctrine is more subtle and difficult to grasp than it might appear. One of its subtleties that eluded the district court is that although a statute may be challenged for vagueness either “on its face” or “as applied,” a “facial” vagueness analysis is mutually exclusive from an “as applied” analysis. The threshold question in any vagueness challenge is whether to scrutinize the statute for intolerable vagueness on its face or whether to do so only as the statute is applied in the particular case. The doctrine does not permit a court to conclude that a statute is facially vague and therefore void, yet not void because it is sufficiently definite as applied.
Therefore, we first analyze this case to decide whether facial vagueness review is appropriate. Courts frequently entertain claims of facial overbreadth because of a special solicitude for first amendment freedoms, e.g., Broadrick v. Oklahoma, 413 U.S. 601, 611-12, 93 S.Ct. 2908, 2915, 37 L.Ed.2d 830 (1973), but facial vagueness review is not common because ordinary canons of judicial restraint do not permit a party whose particular conduct is adequately described by a criminal statute “to attack [the statute] because the language would not give similar fair warning with respect to other conduct which might be within its broad and literal ambit.” Parker v. Levy, 417 U.S. 733, 756, 94 S.Ct. 2547, 2562, 41 L.Ed.2d 439 (1974). See also Flipside, 455 U.S. at 495, 102 S.Ct. at 1191; United States v. Mussry, 726 F.2d 1448, 1454 (9th Cir.), cert. denied, — U.S. —, 105 S.Ct. 180, 83 L.Ed.2d 114 (1984). As the Supreme Court has stated, “under our constitutional system courts are not roving commissions assigned to pass judgment on the validity of the Nation’s laws.” Broadrick v. Oklahoma, 413 U.S. at 610-11, 93 S.Ct. at 2915. This consideration limits the strong medicine of striking down statutes as facially vague.
The Supreme Court has explained how to determine whether facial statutory review is appropriate in response to facial overbreadth and vagueness challenges:
In a facial challenge to the over-breadth and vagueness of a law, a court’s first task is to determine whether the enactment reaches a substantial amount of constitutionally protected conduct. If it does not, then the over-breadth challenge must fail. The court should then examine the facial vagueness challenge and, assuming the enactment implicates no constitutionally protected conduct, should uphold the challenge only if the enactment is impermissibly vague in all of its applications. A plaintiff who engages in some conduct that is clearly proscribed cannot complain of the vagueness of the law as applied to the conduct of others. A court should therefore examine the complainant’s conduct before analyzing other hypothetical applications of the law.
Flipside, 455 U.S. at 494-95, 102 S.Ct. at 1191 (footnotes omitted). Thus, assuming [1347]*1347that no constitutional overbreadth problem exists, the Court has recognized that a party has standing to challenge a statute facially, despite the ordinary rule against facial statutory review, if “no standard of conduct is specified at all,” Parker v. Levy, 417 U.S. at 755, 94 S.Ct. at 2561, quoting Coates, 402 U.S. at 614, 91 S.Ct. at 1688; that is, if the statute “is impermissibly vague in all of its applications.” Flipside, 455 U.S. at 497, 102 S.Ct. at 1193.
This analytical approach seems clear, and the only remaining question is whether Kolender requires any modification. In Kolender, the Court allowed a facial vagueness challenge to a statute that required persons who loiter or wander on the streets to provide a “credible and reliable” identification and to account for their presence to an inquiring police officer. See Cal.Penal Code § 647(e) (West 1970). Lawson had been arrested or detained on approximately fifteen occasions pursuant to the statute, but had been tried only twice and convicted once. In commenting on the prior line of cases, the Court pointed out that criminal statutes require a high degree of certainty and emphasized that the case involved arbitrary enforcement of a statute. Kolender, 103 S.Ct. at 1859 n. 8.
The California identification statute struck down in Kolender is a type of statute that has long been disfavored by the courts. It was enacted to replace the even more disfavored California vagrancy statute, which had been partially struck down and generally criticized on constitutional and prudential grounds. See Selected 1960-61 California Legislation, 36 Cal.St. B.J. 643, 801-02 (1961).
The identification statute, however, did not sufficiently improve upon the vagrancy statute to escape criticism, see Note, Constitutional Attacks on Vagrancy Laws, 20 Stan.L.Rev. 782, 788-89 (1968), or eventual invalidation on vagueness grounds by the Supreme Court. See Kolender, 103 S.Ct. at 1860. Although the Court remarked that Kolender was not the sort of case “where further precision in the statutory language is either impossible or impractical,” id., California’s legislative experience emphasizes the unique tension between law enforcement needs in dealing with incipient crime addressed by these types of statutes and the tolerability of the fundamental vagueness in any conceivable “suspicious persons” statute. As the Court stated in Flipside, judgment is necessary to determine “[t]he degree of vagueness that the Constitution tolerates” in a particular situation. Flipside, 455 U.S. at 498, 102 S.Ct. at 1193. The Court in Kolender determined that the Constitution did not tolerate the degree of vagueness inherent in California’s identification statute and thus applied facial review to strike it down. 103 S.Ct. at 1859 (stating “[sjection 647(e), as presently drafted and construed by the state courts, contains no standard for determining what a suspect has to do”) (emphasis added). Arbitrary enforcement of the statute against Lawson had continued over a long period of time and was amply demonstrated in the record.
In addition to applying facial review because of the unusual fact situation in Kolender and the intolerability of the statute’s inherent vagueness, the Court suggested that facial vagueness review was also appropriate because of the statute’s infringement on first amendment freedoms and the right to free movement. See id. at 1859. To the extent this may be a part of the Court’s consideration, facial vagueness analysis becomes the functional equivalent of facial overbreadth analysis and, apparently, adds nothing new to statutory facial consideration. Although we must await further Supreme Court cases to determine finally what interaction there may be between facial overbreadth and vagueness challenges, compare id. with id. at 1865 (White, J., dissenting), some guidance is provided by Regan v. Time, Inc., — U.S. —, 104 S.Ct. 3262, 82 L.Ed.2d 487 (1984). There, the Court refused to apply facial vagueness review to a statute that arguably infringed on first amendment rights “as a matter of both constitutional limitation and prudential restraint.” Id. at -, 104 S.Ct. at 3267-68.
[1348]*1348Regan presents a significant gloss to Kolender because whether a facial vagueness test should be applied was directly before the Court. The dissent specifically argued that Kolender required a facial consideration because the statute arguably provided the government with “virtually unconstrained authority to decide whether [an act] imposes criminal liability ... or not.” Id. at 3284 (Brennan, J., concurring in part and dissenting in part). Until the Supreme Court provides further guidance, it appears that Kolender presented a unique fact situation and that facial vagueness review may still be appropriate only when “the enactment is impermissibly vague in all of its applications.” Flipside, 455 U.S. at 495, 102 S.Ct. at 1191. If Kolender expands the availability of facial vagueness review, however, it does so only if the challenger at least demonstrates implication of “a substantial amount of constitutionally protected conduct.” Id. at 494, 102 S.Ct. at 1191, quoted in Kolender, 103 S.Ct. at 1859 n. 8. Compare Garner v. White, 726 F.2d 1274, 1277 (8th Cir.1984) (Kolender permits facial review if “the law restricts constitutionally protected conduct”), with Ferguson v. Estelle, 718 F.2d 730, 734-35 (5th Cir.1983) (per curiam) (citing Kolender for the proposition that facial review is appropi iate “only ... [when] no standard of conduct is specified at all”).
We agree with the state that Idaho Code § 18-6607 does not impinge on or “chill” any constitutionally protected conduct, substantial or otherwise. Moreover, because this statute does not by nature fall into the disfavored category of statutes like those regulating vagrancy, cf. Flipside, 455 U.S. at 498, 102 S.Ct. at 1193 (nature of statute affects analysis), and because the Idaho Supreme Court has previously applied the statute to specific conduct, it is also not so vague as to specify “no standard of conduct at all” in any application. Therefore, Schwartzmiller is subject to the usual canons of restraint in the exercise of judicial review and may not attack section 18-6607 on its face, but only as applied to his conduct. The district court should have withheld judgment on whether section 18-6607 is vague on its face.
B.
In scrutinizing a statute for intolerable vagueness as applied to specific conduct, courts must “take the statute as though it read precisely as the highest court of the State has interpreted it.” Wainwright v. Stone, 414 U.S. 21, 22-23, 94 S.Ct. 190, 192, 38 L.Ed.2d 179 (1973), quoting Minnesota ex rel. Pearson v. Probate Court, 309 U.S. 270, 273, 60 S.Ct. 523, 525, 84 L.Ed. 744 (1940). Section 18-6607 states that
[a]ny person who shall wilfully and lewdly commit any lewd or lascivious act or acts upon or with the body or any part or member thereof of a minor or child under the age of sixteen (16) years, with the intent of arousing, appealing to, or gratifying the lust or passions or sexual desires of such person or of such minor or child, shall be guilty of a felony and shall be imprisoned in the state prison for a term of not more than life.
Idaho Code § 18-6607 (1979) (now amended by Idaho Code § 18-1508 (Supp.1984)). We now examine this statute as previously interpreted by the Idaho Supreme Court.
Schwartzmiller challenges the district court’s holding that section 18-6607 is constitutionally definite as applied to his convictions for the two counts of anal intercourse. He argues that State v. Wall, 73 Idaho 142, 144, 248 P.2d 222, 223 (1952), could not have warned him that “crimes against nature” and, hence, anal intercourse, fall within section 18-6607, because Wall’s statement to that effect was merely dictum. Alternatively, he argues that because State v. Carringer, 95 Idaho 929, 930, 523 P.2d 532, 533 (1974), might have led him to believe that violence was a required element of a crime against nature, he cannot be charged with having had notice that what he characterizes as nonviolent, consensual acts were criminal. The state, on the other hand, disputes the district court’s holding that section 18-6607 is [1349]*1349unconstitutionally vague as applied to masturbation of a child.
In Wall, the Idaho Supreme Court held that “any acts going to the extent of actual commission of the infamous crime against nature, where the victim is a child under sixteen years of age, would also constitute a violation of § 18-6607, I.C., proscribing lewd and lascivious acts.” 73 Idaho at 144, 248 P.2d at 223 (emphasis added). Combined with the conclusion of the United States Supreme Court in Rose v. Locke, 423 U.S. at 50-51, 53, 96 S.Ct. at 245, that at common law sodomy is a “crime against nature,” the Idaho decision provided Schwartzmiller with adequate notice and the state with adequate enforcement guidance that anal intercourse with a child is forbidden by section 18-6607. Schwartzmiller’s contentions that the statement in Wall was merely dictum and that Carringer, 95 Idaho at 930-31, 523 P.2d at 533, requires violence to accompany anal intercourse for a section 18-6607 conviction to succeed are flatly wrong. Cf. State v.0 Herr, 97 Idaho 783, 787-89, 554 P.2d 961, 965-67 (1976) (lewd and lascivious conduct found even though no violent action).
State v. Ross, 92 Idaho 709, 711, 716-17, 449 P.2d 369, 371, 376-77 (1968), provided similar notice and guidance regarding masturbation. In Ross, the defendant was convicted pursuant to section 18-6607 for placing his hand inside a young girl’s underwear and fondling her genitals. This gives adequate notice and enforcement guidance that the fondling of a child’s genitals falls within section 18-6607, whether or not the victim is male or female. Thus, Schwartz-miller had adequate notice and the state sufficient enforcement guidance that masturbating a young boy is within the scope of section 18-6607.
Finally, State v. Iverson, 77 Idaho 103, 107, 109, 289 P.2d 603, 604-05 (1955), provided sufficient notice and enforcement guidance that attempted anal intercourse violates section 18-6607. The court in Iverson upheld a conviction under section 18-6607 for attempted anal intercourse. Id., at 109, 289 P.2d at 605. Although the incident in Iverson involved considerable violence, not present here, see id., at 107, 289 P.2d at 604, violence is relevant only to the issue of appropriate sentencing, and not to whether an act constitutes a violation of section 18-6607. Thus, the defendant in Iverson was sentenced to life imprisonment for his violent attempt, while Schwartzmiller was sentenced to only five years for both masturbating and attempting anal intercourse with his victim.
V
Schwartzmiller argues that, even if section 18-6607 is sufficiently definite to meet constitutional due process standards, his conviction must be reversed because under an Idaho rule of evidence he was denied the opportunity to cross-examine the minor victims regarding their consent. This violated his right to due process, he argues, because the rule prevents some defendants from showing that the minor was the aggressor and the only party with the specific intent to arouse sexual passions. The state rejoins that Schwartzmiller did not raise this particular argument in the state proceedings, and thus it is not properly before us.
It does not appear from either the Idaho Supreme Court opinion, see State v. Schwartzmiller, 107 Idaho 89, 685 P.2d 830, 832-34 (1984), or from the record excerpts, that Schwartzmiller made his “aggressive minor” argument in state court. He did present to the Idaho Supreme Court a different claim that the trial court’s refusal to permit cross-examination of the “State’s key witness” concerning previous juvenile adjudications, or concerning one boy’s alleged false accusation of another person for similar acts, violated his constitutional right of confrontation. Id., at 92, 685 P.2d at 832-33. The exhaustion of state remedies doctrine limits the issues a habeas corpus petitioner may raise in federal court to the “same claims” that are “fairly” presented to the highest state court. See Jackson v. Cupp, 693 F.2d at 869. These claims are not the same and exhaustion thus has not been demonstrated.
[1350]*1350AFFIRMED IN PART; REVERSED IN PART.