<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[151777] trunk/base/src/port1.0</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="https://trac.macports.org/changeset/151777">151777</a></dd>
<dt>Author</dt> <dd>cal@macports.org</dd>
<dt>Date</dt> <dd>2016-08-21 15:50:30 -0700 (Sun, 21 Aug 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>base: porttrace: Do not store duplicate violations
The violations list became slow for large builds, which could be noticed
especially when software uses Qt (which creates a large number of false
positive violations in trace mode at the moment due to the use of directory
symlinks).
Replace the current list that kept duplicates with a list that will deduplicate
and automatically sort in O(log n).
Add a unit test to ensure that the implementation works as expected.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkbasesrcport10porttracetcl">trunk/base/src/port1.0/porttrace.tcl</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkbasesrcport10testsporttracetest">trunk/base/src/port1.0/tests/porttrace.test</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkbasesrcport10porttracetcl"></a>
<div class="modfile"><h4>Modified: trunk/base/src/port1.0/porttrace.tcl (151776 => 151777)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/base/src/port1.0/porttrace.tcl 2016-08-21 22:47:55 UTC (rev 151776)
+++ trunk/base/src/port1.0/porttrace.tcl 2016-08-21 22:50:30 UTC (rev 151777)
</span><span class="lines">@@ -48,12 +48,13 @@
</span><span class="cx"> variable thread
</span><span class="cx">
</span><span class="cx"> ##
</span><del>- # A list of files to which access was denied by trace mode.
</del><ins>+ # An ordered duplicate-free list of files to which access was denied by
+ # trace mode.
</ins><span class="cx"> variable sandbox_violation_list [list]
</span><span class="cx">
</span><span class="cx"> ##
</span><del>- # A list of files inside the MacPorts prefix but unknown to MacPorts that
- # were used by the current trace session.
</del><ins>+ # An ordered duplicate-free list of files inside the MacPorts prefix but
+ # unknown to MacPorts that were used by the current trace session.
</ins><span class="cx"> variable sandbox_unknown_list [list]
</span><span class="cx">
</span><span class="cx"> proc appendEntry {sandbox path action} {
</span><span class="lines">@@ -466,7 +467,7 @@
</span><span class="cx"> proc slave_add_sandbox_violation {path} {
</span><span class="cx"> variable sandbox_violation_list
</span><span class="cx">
</span><del>- lappend sandbox_violation_list $path
</del><ins>+ sorted_list_insert sandbox_violation_list $path
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> ##
</span><span class="lines">@@ -492,6 +493,36 @@
</span><span class="cx"> proc slave_add_sandbox_unknown {path} {
</span><span class="cx"> variable sandbox_unknown_list
</span><span class="cx">
</span><del>- lappend sandbox_unknown_list $path
</del><ins>+ sorted_list_insert sandbox_unknown_list $path
</ins><span class="cx"> }
</span><ins>+
+ ##
+ # Insert an element into a sorted list, keeping the list sorted. If the
+ # element is already present in the list, do nothing. This should run in
+ # O(log n) to be useful.
+ proc sorted_list_insert {listname element} {
+ upvar $listname l
+
+ set rboundary [llength $l]
+ set lboundary 0
+
+ while {[set distance [expr {$rboundary - $lboundary}]] > 0} {
+ set index [expr {$lboundary + ($distance / 2)}]
+
+ set cmp [string compare $element [lindex $l $index]]
+ if {$cmp == 0} {
+ # element already present, do nothing
+ return
+ } elseif {$cmp < 0} {
+ # continue left
+ set rboundary $index
+ } else {
+ # continue right
+ set lboundary [expr {$index + 1}]
+ }
+ }
+
+ # we're at the end, lets insert here
+ set l [linsert $l $lboundary $element]
+ }
</ins><span class="cx"> }
</span></span></pre></div>
<a id="trunkbasesrcport10testsporttracetest"></a>
<div class="addfile"><h4>Added: trunk/base/src/port1.0/tests/porttrace.test (0 => 151777)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/base/src/port1.0/tests/porttrace.test (rev 0)
+++ trunk/base/src/port1.0/tests/porttrace.test 2016-08-21 22:50:30 UTC (rev 151777)
</span><span class="lines">@@ -0,0 +1,42 @@
</span><ins>+# -*- coding: utf-8; mode: tcl; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- vim:fenc=utf-8:ft=tcl:et:sw=4:ts=4:sts=4
+
+package require tcltest 2
+namespace import tcltest::*
+
+set pwd [file dirname [file normalize $argv0]]
+
+package require Tclx
+package require porttrace 1.0
+
+test sorted_list_insert {
+ Test porttrace::sorted_list_insert
+} -setup {
+ set numbers [list]
+ for {set i 0} {$i < 1000} {incr i} {
+ lappend numbers [random 2000]
+ }
+ set sorted_numbers [lsort -unique $numbers]
+} -body {
+ # random is provided by TclX
+ set l [list]
+
+ foreach num $numbers {
+ porttrace::sorted_list_insert l $num
+ }
+
+ set differences [list]
+ set l_len [llength $l]
+ set s_len [llength $sorted_numbers]
+ if {$l_len != $s_len} {
+ lappend differences [list "length" $l_len $s_len]
+ }
+ for {set i 0} {$i < [expr {min($l_len, $s_len)}]} {incr i} {
+ if {[lindex $l $i] ne [lindex $sorted_numbers $i]} {
+ lappend differences [list $i [lindex $l $i] [lindex $sorted_numbers $i]]
+ }
+ }
+
+ return $differences
+} -result [list]
+
+cleanupTests
</ins></span></pre>
</div>
</div>
</body>
</html>