Performs a depth-first (document order) XPath search, and returns the
 first match.  This is the fastest, lightest way to return a single result.

 FIXME: This method is incomplete!
344211
def first( path_stack, node )
      #puts "#{depth}) Entering match( #{path.inspect}, #{tree.inspect} )"
      return nil if path.size == 0

      case path[0]
      when :document
        # do nothing 
        return first( path[1..-1], node )
      when :child
        #for c in node.children
        node.children.each do |c|
          #puts "#{depth}) CHILD checking #{name(c)}"
          r = first( path[1..-1], c )
          #puts "#{depth}) RETURNING #{r.inspect}" if r
          return r if r
        end
      when :qname
        name = path[2]
        #puts "#{depth}) QNAME #{name(tree)} == #{name} (path => #{path.size})"
        if node.name == name
          #puts "#{depth}) RETURNING #{tree.inspect}" if path.size == 3
          return node if path.size == 3
          return first( path[3..-1], node )
        else
          return nil
        end
      when :descendant_or_self
        r = first( path[1..-1], node )
        return r if r
        #for c in node.children
        node.children.each do |c|
          r = first( path, c )
          return r if r
        end
      when :node
        return first( path[1..-1], node )
      when :any
        return first( path[1..-1], node )
      end
      return nil
    end
1270507
def depth_first_recurse(node = nil, depth = 0, &block)
      node = self if node == nil
      yield node, depth
      node.children.each do |child|
        depth_first_recurse(child, depth+1, &block)
      end
    end
1184240
def getBriefAndDetailedRST(textRoot, node):
    '''
    
    '''
    node_xml_contents = utils.nodeCompoundXMLContents(node)
    if not node_xml_contents:
        return "", ""

    try:
        node_soup = BeautifulSoup(node_xml_contents, "lxml-xml")
    except:
        utils.fancyError("Unable to parse [{0}] xml using BeautifulSoup".format(node.name))

    try:
        # In the file xml definitions, things such as enums or defines are listed inside
        # of <sectiondef> tags, which may have some nested <briefdescription> or
        # <detaileddescription> tags.  So as long as we make sure not to search
        # recursively, then the following will extract the file descriptions only
        # process the brief description if provided
        brief      = node_soup.doxygen.compounddef.find_all("briefdescription", recursive=False)
        brief_desc = ""
        if len(brief) == 1:
            brief = brief[0]
            # Empty descriptions will usually get parsed as a single newline, which we
            # want to ignore ;)
            if not brief.get_text().isspace():
                brief_desc = convertDescriptionToRST(textRoot, node, brief, None)

        # process the detailed description if provided
        detailed      = node_soup.doxygen.compounddef.find_all("detaileddescription", recursive=False)
        detailed_desc = ""
        if len(detailed) == 1:
            detailed = detailed[0]
            if not detailed.get_text().isspace():
                detailed_desc = convertDescriptionToRST(textRoot, node, detailed, "Detailed Description")

        return brief_desc, detailed_desc
    except:
        utils.fancyError(
            "Could not acquire soup.doxygen.compounddef; likely not a doxygen xml file."
        )
1195769
def firstElementChild(self) -> Optional[AbstractNode]:
        
        for child in self.childNodes:
            if child.nodeType == Node.ELEMENT_NODE:
                return child
        return None
675407
function ancestorMatch(el, tokens, dividedTokens, root) {
      var cand
      // recursively work backwards through the tokens and up the dom, covering all options
      function crawl(e, i, p) {
        while (p = walker[dividedTokens[i]](p, e)) {
          if (isNode(p) && (found = interpret.apply(p, q(tokens[i])))) {
            if (i) {
              if (cand = crawl(p, i - 1, p)) return cand
            } else return p
          }
        }
      }
      return (cand = crawl(el, tokens.length - 1, el)) && (!root || isAncestor(cand, root))
    }
801269
def find_first_match(basedir, string):
    
    matches = find(basedir, string)
    return matches[0] if matches else matches
1346323
def _depth_first_search(self, target_id, layer_id_list, node_list):
        """"""
        assert len(node_list) <= self.n_nodes
        u = node_list[-1]
        if u == target_id:
            return True

        for v, layer_id in self.adj_list[u]:
            layer_id_list.append(layer_id)
            node_list.append(v)
            if self._depth_first_search(target_id, layer_id_list, node_list):
                return True
            layer_id_list.pop()
            node_list.pop()

        return False
593487
public final void xpathSeparator() throws RecognitionException {
		try {
			// src/main/resources/org/drools/compiler/lang/DRL6Expressions.g:560:5: ( DIV | QUESTION_DIV )
			// src/main/resources/org/drools/compiler/lang/DRL6Expressions.g:
			{
			if ( input.LA(1)==DIV||input.LA(1)==QUESTION_DIV ) {
				input.consume();
				state.errorRecovery=false;
				state.failed=false;
			}
			else {
				if (state.backtracking>0) {state.failed=true; return;}
				MismatchedSetException mse = new MismatchedSetException(null,input);
				throw mse;
			}
			}

		}

		catch (RecognitionException re) {
		    throw re;
		}

		finally {
			// do for sure before leaving
		}
	}
771736
def precedes(self, other):
        """"""
        try:
            ancestor = next(commonancestors(AbstractElement, self, other))
        except StopIteration:
            raise Exception("Elements share no common ancestor")
        #now we just do a depth first search and see who comes first
        def callback(e):
            if e is self:
                return True
            elif e is other:
                return False
            return None
        result = ancestor.depthfirstsearch(callback)
        if result is None:
            raise Exception("Unable to find relation between elements! (shouldn't happen)")
        return result
1000620
public static function getFirstElementByXpath($node, $xpath_query, $namespaces = array())
    {
        if(is_a($node, 'DOMDocument'))
        {
            $xpath = new DOMXPath($node);
        }
        elseif(is_a($node, 'DOMNode'))
        {
            $xpath = new DOMXPath($node->ownerDocument);
        }
        else
        {
            return null;
        }

        foreach($namespaces as $prefix => $namespaceURI)
        {
            $xpath->registerNamespace($prefix, $namespaceURI);
        }

        $node_list = $xpath->query($xpath_query, $node);

        if ($node_list->length > 0)
        {
            return $node_list->item(0);
        }
        else
        {
            return null;
        }
    }
633318
def match(node)
      raise_unless_xpath!(node)
      pos = node.xpath("descendant::pos").first
      return nil if pos.nil?
      { matched: node.respond_to?(:name) ? node.name : "",
        line: pos["line"].to_i, column: pos["column"].to_i }
    end
210585
def findFirstPar(theDict, name, _depth=0):
    

    for key in theDict:
        val = theDict[key]
#       print _depth*'   ', key, str(val)[:40]
        if isinstance(val, dict):
            retval = findFirstPar(val, name, _depth=_depth+1) # recurse
            if retval is not None:
                return retval
            # else keep looking
        else:
            if key == name:
                return theDict, theDict[name]
            # else keep looking
    # if we get here then we have searched this whole (sub)-section and its
    # descendants, and found no matches.  only raise if we are at the top.
    if _depth == 0:
        raise KeyError(name)
    else:
        return None
819148
def traverse_depth_first_post_order(self, callback):
        
        # a. Reimplement without python lists?..
        # b. Interface will require it to have not internal nodes only?..
        #    (but actually this implementation gives a ~2x gain of performance)
        last_interval = None
        n = len(self.suftab)
        stack = [[0, 0, None, []]]  # <l, i, j, children>
        for i in xrange(1, n):
            lb = i - 1
            while self.lcptab[i] < stack[-1][0]:
                stack[-1][2] = i - 1
                last_interval = stack.pop()
                callback(last_interval)
                lb = last_interval[1]
                if self.lcptab[i] <= stack[-1][0]:
                    stack[-1][3].append(last_interval)
                    last_interval = None
            if self.lcptab[i] > stack[-1][0]:
                if last_interval:
                    stack.append([self.lcptab[i], lb, None, [last_interval]])
                    last_interval = None
                else:
                    stack.append([self.lcptab[i], lb, None, []])
        stack[-1][2] = n - 1
        callback(stack[-1])
950642
public static Node getFirstNode(Document doc, String xPathExpression) {
			try {

				XPathFactory xPathfactory = XPathFactory.newInstance();
				XPath xpath = xPathfactory.newXPath();
				XPathExpression expr;
				expr = xpath.compile(xPathExpression);
				NodeList nl = (NodeList) expr.evaluate(doc, XPathConstants.NODESET);
				return nl.item(0);

			} catch (XPathExpressionException e) {
				e.printStackTrace();
			}

			return null;
		}
489498
def match_seq(self, nodes, results=None):
        
        if len(nodes) != 1:
            return False
        return self.match(nodes[0], results)
95126
private boolean goToNextDoc() throws IOException {
    if (docId == NO_MORE_DOCS) {
      return true;
    } else {
      // try to find docId with match for all items from sequence
      Integer spanDocId;
      Integer newDocId = null;
      Integer minOptionalDocId = null;
      boolean allItemsOptional = true;
      for (QueueItem item : queueSpans) {
        if (!item.sequenceSpans.optional) {
          allItemsOptional = false;
        }
        if (!item.noMoreDocs) {
          if (item.sequenceSpans.spans == null) {
            spanDocId = NO_MORE_DOCS;
          } else if (newDocId == null) {
            spanDocId = item.sequenceSpans.spans.nextDoc();
          } else {
            if (!item.sequenceSpans.optional) {
              spanDocId = item.sequenceSpans.spans.advance(newDocId);
            } else {
              if (item.sequenceSpans.spans.docID() == -1
                  || newDocId > item.sequenceSpans.spans.docID()) {
                spanDocId = item.sequenceSpans.spans.advance(newDocId);
              } else {
                spanDocId = item.sequenceSpans.spans.docID();
              }
            }
          }
          if (spanDocId.equals(NO_MORE_DOCS)) {
            item.noMoreDocs = true;
            if (!item.sequenceSpans.optional) {
              // a not optional span has NO_MORE_DOCS: stop
              docId = NO_MORE_DOCS;
              return true;
            }
          } else if (!spanDocId.equals(newDocId)) {
            // last found spanDocId not equal to potential new docId
            if (newDocId != null) {
              if (!item.sequenceSpans.optional) {
                // move also previous spans to at least spanDocId
                advance(spanDocId);
                return true;
              }
              // define potential new docId
            } else {
              if (!item.sequenceSpans.optional) {
                // previous optional span with lower docId
                if ((minOptionalDocId != null)
                    && (minOptionalDocId < spanDocId)) {
                  advance(spanDocId);
                  return true;
                } else {
                  // use spanDocId as potential newDocId
                  newDocId = spanDocId;
                }
              } else {
                // remember minimum docId optional spans
                minOptionalDocId = (minOptionalDocId == null) ? spanDocId
                    : Math.min(minOptionalDocId, spanDocId);
              }
            }
          }
        }
      }
      // if all items are optional
      if (allItemsOptional && newDocId == null && minOptionalDocId != null) {
        newDocId = minOptionalDocId;
      }
      // nothing found
      if (newDocId == null) {
        docId = NO_MORE_DOCS;
        return true;
      } else {
        docId = newDocId;
        ignoreItem.advanceToDoc(docId);
        // try and glue together
        if (findMatches()) {
          return true;
          // no matches
        } else {
          resetQueue();
          return false;
        }
      }
    }
  }
1368716
def find_element_by_xpath(self, xpath):
        
        from sdklib.html.elem import Elem5lib

        return Elem5lib(self.html_obj.find(self._convert_xpath(xpath)))